perm filename NOTES[1,RWF] blob
sn#320650 filedate 1979-10-15 generic text, type C, neo UTF8
COMMENT ā VALID 00079 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00008 00002 Notes on Programming in SAIL
C00011 00003 %Commands%.
C00015 00004
C00017 00005 %Iteration.%
C00021 00006 V will be given the value E , and C will be executed.
C00025 00007 Exercise: Find the right expression E so that the command:
C00028 00008 %Example%.
C00030 00009 BEGIN
C00034 00010 %Blocks%.
C00038 00011 To make the extent and structure of blocks immediately apparent to the
C00040 00012 %Example%.
C00042 00013 Exercise. Write a program which prints the first 36 numbers in the form:
C00045 00014 %About Definitions%.
C00049 00015 In describing the grammatical structure of SAIL, we will use the script
C00054 00016 # A printing command has the form
C00055 00017
C00057 00018 In the table above, the right-hand column lists a number of operations
C00061 00019 %Spacing%.
C00063 00020 %Printing Format%.
C00068 00021 %String Constants%.
C00071 00022 %Example%.
C00073 00023 If we had available a fantastically rich and expressive programming
C00077 00024 BEGIN
C00080 00025 TABLE OF LOGARITHMS
C00086 00026
C00087 00027 Solutions, omitting declarations, etc.:
C00089 00028 %Comments in Programs%.
C00092 00029 %Programming Superstitions%.
C00097 00030 (1) Because 100 numbers were printed, a PRINT command must have been iterated.
C00100 00031 %Program Variables and Assignment%.
C00104 00032 to create a variable A which could take on only whole-number values,
C00107 00033 REAL S
C00111 00034 When this program is executed, the results printed at the terminal might be
C00114 00035 %Conditional Commands%.
C00117 00036 %Example%.
C00120 00037 The large number of dots and asterisks suggests using an iteration, but since
C00125 00038 It has the second meaning where an ELSE could be matched with more than one
C00129 00039 %Logical Connectives%.
C00132 00040 are also Boolean expressions. The first is true only when a and a are
C00134 00041 FOR R:=1 STEP 1 UNTIL 5 DO
C00138 00042 1.1 Compute in turn f ,f ,...,f , where f = 1 , f = 1 , and
C00141 00043 We approach such problems by the following procedure:
C00145 00044 We see that the source of the difficulty is that the old value of A is
C00149 00045 %Constructing Correct Programs%.
C00153 00046 IF E THEN
C00155 00047 FOR J:=1 STEP 1 UNTIL 2 DO PRINT("DD")
C00159 00048 (1) If B is the block containing a declaration of the identifier I , then
C00163 00049 f f f
C00167 00050 In an expression like X[I+J] where X is an array name, the expression
C00171 00051 %Example%.
C00174 00052 %Definitions in SAIL%.
C00177 00053 %Example%.
C00180 00054 is a complete program, which otherwise would have been several lines longer.
C00184 00055 %Example preamble using SETPRINT%:
C00186 00056 The following is a program which uses most of the capabilities of the
C00189 00057 The following program takes its input from two files, ESTIMT.DAT and
C00192 00058 %Rounding and Truncation%.
C00196 00059 %Desk Checking of Programs%.
C00200 00060 Example:
C00202 00061 %Diagnosing Incorrect Results of Programs%.
C00207 00062 %Computing with Strings in SAIL%.
C00211 00063 The function LOP(SV) has as its value the first character of the string
C00215 00064 %Procedures as a Way of Defining Functions in SAIL%.
C00219 00065 A related method, when X is converging to a target value, is to keep the
C00221 00066 %Design of Conditional Commands%.
C00225 00067 Here, however, we need only consider values of X,Y which fall in the
C00228 00068
C00231 00069 %Exercise%. Simplify the above program by using the logical connectives in
C00234 00070 In most usage of DIV and MOD, a and a are positive numbers. In this
C00238 00071 The design of this program is simplified by observing:
C00241 00072 The example below shows how a command containing a conditional expression
C00243 00073 The following is not valid for SAIL (FLOOR and ROUND).
C00245 00074 %Example%.
C00247 00075 %Avoiding Redundant Effort in Programming%.
C00250 00076 Suppose we want to compute e for a small value of x , using the
C00253 00077 Q C S
C00257 00078 In order to get it and to save the useful information needed for the next
C00261 00079
C00262 ENDMK
Cā;
Notes on Programming in SAIL
Robert W. Floyd
Copyright 1977
%Programs%.
A %program% in SAIL is an order to the computer, describing how a certain
computation is to be carried out. This order contains both information about
the resources the computer will need to perform the computation, and detailed
instructions about the sequence of information processing operations needed.
This information, and these instructions, are written in precisely defined
notations, as %declarations% and %commands% respectively. A program consists
of the word BEGIN, then a series of declarations, then a series of commands,
then the word END. The declarations and commands are all separated from each
other by semicolons. Symbolically, a program has the form
BEGIN D ;D ;...;D ;C ;C ;...;C END
1 2 d 1 2 c
where the declarations and commands will usually be on separate lines for
legibility.
%Declarations%.
The first declaration in a program will always be
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE
(This bit of gibberish informs the SAIL translator of the meaning of some of the
notations we will be using. Its meaning will be explained much later.) The
other declarations, for the moment, will tell the translator the names we plan
to use for some variables which will have integer (whole number) values. To say
that we plan to use three such variables and call them J , N , and EUCLID ,
we would include in the program the declaration
INTEGER J, N, EUCLID
%Commands%.
Until further notice, every program you write should have as its first
two commands
SETPRINT(filename,"B");
SETFORMAT(13,7);
where the file name should be the name, in quotes, of the file where you want
your results to appear. For example, if the program is in the file called
MYPROG.SAI, the results might be sent to file MYPROG.OUT by using
SETPRINT("MYPROG.OUT","B")
The SETPRINT command controls where the results of the program go; if omitted,
they go only to your terminal. The SETFORMAT command controls the form in
which numbers are printed. Using the arguments 13 and 7 , they are
printed with enough blank spaces to make up a total of 13 positions across
the line, rounding decimal numbers off to seven digits.
%Print Commands%.
The commands will be of many kinds, but every program will include at least
one command to print its results so that we can see them. (Most of a program's
computation will never be seen by humans. We will often have it print not only
the final results we want, but some intermediate numbers for checking purposes.)
The command which orders the computer to print a number, say 1977, is
PRINT(1977)
If we want to print several numbers, we include them all in the parentheses,
separated by commas. The command
PRINT(1776, 1977, 1984)
will make the computer print
1776 1977 1984
If we don't know the actual number we want printed, but do know an expression
for it, for example as a sum or product of other numbers, we can use that
expression in the printing command:
PRINT(3+5, 22/7, SIN(3.1415927/4))
orders the computer to print
8 3.1428571 0.70710678
If we want messages interspersed with the printed numbers, we can enclose
them in quotation marks " ", otherwise treating them like the numbers in the
printing command:
PRINT("PI IS ABOUT", 22/7, "THE U.S. IS", 1977-1776, "YEARS OLD")
orders the computer to print:
PI IS ABOUT 3.142857 THE U.S. IS 201 YEARS OLD
(Notice that the computer is saying these things because it has been told to,
not because they are true. Computers are not interested in truth.)
If we want to print information on several lines, we can include the word
NEWLINE in a print command to cause subsequent printing to start on the next
line. A short program using this:
BEGIN
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
SETPRINT("SQRS.OUT","B");
SETFORMAT(13,7);
PRINT("SHORT TABLE OF PERFECT SQUARES", NEWLINE);
PRINT(1*1, 2*2, 3*3, 4*4, 5*5, NEWLINE, 6*6, 7*7, 8*8, 9*9, 10*10)
END
will print this:
SHORT TABLE OF PERFECT SQUARES
1 4 9 16 25
36 49 64 81 100
(The asterisk, * , is used as a multiplication symbol in SAIL. The more
traditional x and . are too easily confused with the letter x and the
decimal point to be satisfactory in computer languages.)
%Iteration.%
Our last example could as well have been done by a hand calculator as by
a computer, since we had to write a separate formula for each number we wanted
to print. Since there was a general pattern to all these formulas, it would be
better if we could write a command that would briefly describe this general
pattern. If, for example, we wanted to write the first 100 square roots on
separate lines, we could use these commands:
PRINT(SQRT(1), NEWLINE);
PRINT(SQRT(2), NEWLINE);
PRINT(SQRT(3), NEWLINE);
.
.
.
PRINT(SQRT(100), NEWLINE)
Here are two elements in the pattern.
(1) Every command is of the form
PRINT(SQRT(I), NEWLINE)
for some number I .
(2) The series of values that I takes on starts wih 1 , always increases
by 1 , and ends at 100 .
We have completely described the pattern. We can say the same thing in
SAIL with the program
BEGIN
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
INTEGER I;
FOR I := 1 STEP 1 UNTIL 100 DO
PRINT(SQRT (I), NEWLINE)
END
Here the third line is a declaration for the variable I . The fourth line is
an %iterative clause%, causing the immediately following command to be repeated.
It also gives I the values 1,2,3,...,99,100 for the successive repetitions,
then quits. Such commands make possible the effective use of the vast speed
of present-day computers, by specifying very concisely a large number of
similar operations. (We shall later show other types of iterative clause.)
A significant part of the computer programmer's task is to find a way of
viewing a particular problem as a series of similar operations which can be
expressed as an iteration.
Generally, if V is a variable, E , E , E are expressions with
1 2 3
numerical values, and C is a command, we can write an %iterative command% of
the form:
FOR V := E STEP E UNTIL E DO C
1 2 3
with the effect that
V will be given the value E , and C will be executed.
1
V will be increased by the value E , and C will be executed.
2
V will again be increased by E , and C executed.
2
Etc.
As soon as V gets larger than E , the process stops (even if C has not
3
even been executed once); the iterative command is then finished.
%Example%.
FOR A := 3 STEP 2 UNTIL 9 DO
PRINT(A,A-1)
prints:
3 2 5 4 7 6 9 8
so does:
FOR A := 3 STEP 2 UNTIL 10 DO
PRINT(A,A-1)
so does:
FOR B := 0 STEP 1 UNTIL 3 DO
PRINT(2*B+3, 2*B+2)
Exercise: Write a program which will, for each number from 2 to 100 ,
print on one line the number, its square, its cube, and its square root.
Exercise: Write a program which will print a temperature conversion table
from degrees Centigrade to degrees Fahrenheit. The relevant formula is
F = 9C/5 + 32 , where C is the Centigrade temperature and F is the
Fahrenheit temperature. The table should go from -40 degrees to 50 degrees
Centigrade. (Warning: the formula as given is not in the SAIL language.)
Exercise: Write a program which will, for each number from 10 to 99 ,
print the number and its logarithm.
Exercise: Write a program which will, for each number in the sequence
0, 0.01, 0.02, ..., 1.00 , print the number, its sine, and its cosine.
SAIL uses radian measure for angles.
Warning: In iterative clauses, where the iteration variable has been declared
to be an integer, E , E , and E must always take on integer (whole
1 2 3
number) values, so that the iteration variable will run through a sequence of
equally spaced %integer% values.
Exercise: Find the right expression E so that the command:
FOR I := 1 STEP 1 UNTIL 6 DO
PRINT(E)
will print:
7 11 15 19 23 27 .
Find another E which makes it print:
20 13 6 -1 -8 -15 .
Suggest a general rule.
Do the same thing for the command
FOR I := 0 STEP 1 UNTIL 5 DO
PRINT(E)
Is this easier?
The meaning of the command below, in which an iterative command is itself
iterated (such a command is called a %nested% iteration),is interpreted by
first substituting 1 and 2 for I , to get the series of commands in the
second column, and then substituting the appropriate numbers for J , to get
the third column. The order of substitution is important.
FOR I := 1 STEP 1 UNTIL 2 DO FOR J := 1 STEP 1 UNTIL 4 DO
FOR J := I STEP 1 UNTIL 4 DO PRINT(1/J);
PRINT(I/J) FOR J := 2 STEP 1 UNTIL 4 DO
PRINT(2/J)
PRINT(1/1);
PRINT(1/2);
PRINT(1/3);
PRINT(1/4);
PRINT(2/2);
PRINT(2/3);
PRINT(2/4);
The above command prints
1.00000 0.500000 0.333333 0.250000 1.00000 0.666667 0.500000
Exercise: Find the sequence of printing commands equivalent to
FOR K := 1 STEP 1 UNTIL 3 DO
FOR L := K STEP 1 UNTIL 3 DO
PRINT(K*L)
%Example%.
To write a program to print the multiplication tables for numbers
1 through 10 , as shown below:
1 x 1 = 1
1 x 2 = 2
.
.
.
1 x 10 = 10
2 x 1 = 2
2 x 2 = 4
.
.
2 x 10 = 20
3 x 1 = 3
.
.
.
3 x 10 = 30
.
.
.
10 x 10 = 100
We could print (say) the third group of lines by the command
FOR J := 1 STEP 1 UNTIL 10 DO PRINT(3,"*",J,"=",3*J)
the fourth line by
FOR J := 1 STEP 1 UNTIL 10 DO PRINT(4,"*",J,"=",4*J)
Generally, we may print the I-th line by the command
FOR J := 1 STEP 1 UNTIL 10 DO PRINT(I,"*",J,"=",I*J)
with the appropriate number substituted for I . On the other hand, the
entire program consists of writing lines 1 though 10; thus the program is
FOR I := 1 STEP 1 UNTIL 10 DO
Print the I-th line
Combining these, we get the complete SAIL program:
BEGIN
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
INTEGER I,J;
SETPRINT("MULTBL.OUT","B");
SETFORMAT(13,7);
FOR I := 1 STEP 1 UNTIL 10 DO
FOR J := 1 STEP 1 UNTIL 10 DO
PRINT(I,"*",J,"=",I*J)
END
which is equivalent to these programs
FOR J := 1 STEP 1 UNTIL 10 DO PRINT(1,"*",1,"=",1);
PRINT(1,"*",J,"=",1*J) PRINT(1,"*",2,"=",2);
PRINT(1,"*",3,"=",3);
.
.
.
PRINT(1,"*",10,"=",10);
FOR J := 1 STEP 1 UNTIL 10 DO PRINT(2,"*",1,"=",2);
PRINT(2,"*",J,"=",2*J) PRINT(2,"*",2,"=",4);
. .
. .
.
FOR J := 1 STEP 1 UNTIL 10 DO PRINT(10,"*",1,"=",10);
PRINT(10,"*",J,"=",10*J) PRINT(10,"*",2,"=",20);
.
.
.
PRINT(10,"*",10,"=",100)
which prints
1 x 1 = 1
1 x 2 = 2
.
.
.
10 x 10 = 100
(We shall use this scroll shape to show the results from a program.)
Exercise. Find a nested iteration to print the numbers
10, 11, 20, 21, 22, 30, 31, 32, 33, 40, 41, 42, 43, 44 .
(Hint: break the sequence up into groups, and find an iterative command
for each group. Look for the common features of all the iterative commands.)
Exercise: Print the integers between 1 and 100 which are %not% perfect
squares, i.e.,
2 3 5 6 7 8 10 11 12 13 14 15 17 ... 99 .
(To the teacher: there are several ways to do this, even using the limited
repertory of operations thus far covered. Class discussion of their
efficiencies may be rewarding.)
%Blocks%.
Suppose we want the computer to print a large triangle of asterisks, like
this
*
**
***
****
*****
******
but fifty lines high. The pattern is obvious. Similarly, how to print each
particular line is obvious; for the 43rd, we need the commands
FOR I := 1 UNTIL 43 DO
PRINT("*");
PRINT(NEWLINE)
To avoid writing this out 50 times, changing only the number 43 , we see
that it has the general pattern
FOR I := 1 STEP 1 UNTIL L DO
PRINT("*");
PRINT(NEWLINE)
and that an iterative command like
FOR L := 1 STEP 1 UNTIL 50 DO
would give L the right sequence of values. But if we try putting them
together in a program,
FOR L := 1 STEP 1 UNTIL 50 DO
FOR I := 1 STEP 1 UNTIL L DO
PRINT("*");
PRINT(NEWLINE)
we get, not a triangle, but a number of solid lines of asterisks, totaling
1275 . Why didn't PRINT(NEWLINE) get executed while L was 1 ,
immediately after executing the I iteration once and printing one asterisk?
The reason is that an iterative clause only applies to the immediately
following command. The iterative clause that uses L causes repetition of
the next two lines, which are a single complete command. The last line is a
separate command. Somehow we need to tie these two into one single command.
Suppose C ,C ,...,C are any commands. To form a single command which
1 2 n
has the effect of executing C , then C , etc., through C , we may write
1 2 n
the %block% of commands
BEGIN C ; C ; ... C END
1 2 n
The block can then be treated as a whole, for the purposes of iteration and
for other purposes which we shall encounter. The words BEGIN and END serve
as parentheses around commands.
To make the extent and structure of blocks immediately apparent to the
eye when reading programs, it is desirable to write a block in the form
BEGIN
C ;
1
C ;
2
.
.
.
C
n
END
where each command of the block begins on a new line and the entire block is
indented further than the line which precedes the block.
To see the difference that use of blocks makes,
FOR I := 1 STEP 1 UNTIL 3 DO C1; C2; C3
has the effect of C1; C1; C1; C2; C3 , but
FOR I := 1 STEP 1 UNTIL 3 DO BEGIN C1; C2; C3 END
has the effect of C1; C2; C3; C1; C2; C3; C1; C2; C3. Going back to our
triangle problem, we see that we need this program:
BEGIN
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
INTEGER I, L;
FOR L := 1 STEP 1 UNTIL 50 DO
BEGIN
FOR I := 1 STEP 1 UNTIL L DO
PRINT("*");
PRINT(NEWLINE)
END
END
%Example%.
To print this chessboard pattern
XXXOOOXXXOOOXXXOOOXXXOOO
XXXOOOXXXOOOXXXOOOXXXOOO
XXXOOOXXXOOOXXXOOOXXXOOO
OOOXXXOOOXXXOOOXXXOOOXXX
OOOXXXOOOXXXOOOXXXOOOXXX
OOOXXXOOOXXXOOOXXXOOOXXX
. . . . . . . .
. . . . . . . .
. . . . . . . .
OOOXXXOOOXXXOOOXXXOOOXXX
The first six lines can be printed by
FOR I := 1 STEP 1 UNTIL 3 DO
PRINT("XXXOOOXXXOOOXXXOOOXXXOOO",NEWLINE);
FOR I := 1 UNTIL 3 DO
PRINT("OOOXXXOOOXXXOOOXXXOOOXXX",NEWLINE)
Making a block of this and iterating, we get the program
FOR J := 1 STEP 1 UNTIL 4 DO
BEGIN
FOR I := 1 STEP 1 UNTIL 3 DO
PRINT("XXXOOOXXXOOOXXXOOOXXXOOO",NEWLINE);
FOR I := 1 STEP 1 UNTIL 3 DO
PRINT("OOOXXXOOOXXXOOOXXXOOOXXX",NEWLINE)
END
Exercise. Write a program which prints the first 36 numbers in the form:
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 32 33 34 35
(Clue: the i-th line starts with a number i(i-1)/2 . Try first writing a
program which prints only the first number of each line.)
Exercise. Match the pieces of program below to the lines they print.
(1) FOR R := 1 STEP 1 UNTIL 4 DO (i) AB
FOR C := 1 STEP 1 UNTIL R DO AAB
PRINT("A"); AAAB
PRINT("B",NEWLINE) AAAAB
(2) FOR R := 1 STEP 1 UNTIL 4 DO (ii) AAAAAAAAAAB
FOR C := 1 STEP 1 UNTIL R DO
BEGIN
PRINT("A");
PRINT("B",NEWLINE)
END
(3) FOR R := 1 STEP 1 UNTIL 4 DO (iii) AB
BEGIN AB
FOR C := 1 STEP 1 UNTIL R DO B
PRINT("A"); AB
PRINT("B",NEWLINE) B
END B
AB
B
B
B
(4) FOR R := 1 STEP 1 UNTIL 4 DO (iv) AB
BEGIN AB
PRINT("A"); AB
FOR C := 1 STEP 1 UNTIL R DO AB
PRINT("B",NEWLINE) AB
END AB
AB
AB
AB
AB
(5) FOR R := 1 STEP 1 UNTIL 4 DO
BEGIN
FOR C := 1 STEP 1 UNTIL R DO
PRINT("A")
END;
PRINT("B",NEWLINE)
%About Definitions%.
In describing SAIL, we shall distinguish between %syntax%, %semantics%,
and %pragmatics%. (This terminology is due to Carnap.) %Syntax% is the
grammar of the language; it specifies which programs are meaningful, and how a
program is subdivided into meaningful parts. %Semantics% is concerned with
defining meaning; it specifies what each program does when executed, usually
either by saying how the program carries out its actions, or by saying how to
construct a simpler equivalent program. %Pragmatics% is concerned with
practicality; it states what execution of a program will cost, usually as
measured in units of time or money, whether execution of a program will require
more of some resource than is avalable on a particular computer, and what the
value of the results will be (particularly how precisely they are calculated).
For the purposes of syntactic definition, we will eventually give precise
definitions to a number of kinds of things we can write as parts of programs.
Among these are the following:
%Constants%: designate a particular number, word, or object with
which computation is done.
Examples: 2, 3.14159 "MISSISSIPPI"
%Identifiers%: used as names for anything to which a programmer may
give a name: variables, functions, tables, part of programs.
Examples: A, X, SINE, LOGTABLE, A3PQ14, TIME.OF.DAY
%Expressions%: designate a way of computing a value for subsequent
use in the program. Since an expression may contain variables which
have different vaues at different times, the computation which an
expression describes must usually be done again each separate time
the value of the expression is needed.
Examples: X, 13.54, COS(PI/6), A,B-C
%Commands%: designate an action or series of actions to be carried
out by the computer, such as calculations, printing, deciding
between two courses of action, etc.
In describing the grammatical structure of SAIL, we will use the script
letters K, I, E, C, possibly with subscripts, diacritical marks, etc., as
symbols for arbitrary constants, identifiers, expressions, and commands.
For example, the form of an iterative command can be described as
FOR I := E STEP E UNTIL E DO C
1 2 3
where E , E , and E are expressions having integer values, and C is
1 2 3
any command.
We will later introduce other grammatical categories. For each, we will
have a script capital letter to stand for an arbitrary member of that category.
Often it will be necessary to define the meanings of commands, etc., in
which one or more expressions appear, and for which the process of execution
requires evaluation of the expressions. In such circumstances, we will use
the lower case letter a to designate the value of the expression E , i.e.,
the number, word, etc., which results from evaluating E . If E is the
expression (3+5)*12 , the value a is 96 . (More precisely, a is the
number which we designate in the decimal notation by 96 ; in Roman numerals,
a would be designated by XCVI or, in binary notation, by 1100000 , but
would still be the same value.) Similarly, we use a and a' to refer to
1
the values of E and E' respectively. To say concisely that if an
1
expression consists of two smaller expressions connected by an asterisk, the
value of the expression is the product of the values of the two smaller
expressions, we could say
"If E is E *E , then a = a xa ."
1 2 1 2
In general, we use script capital letters in stating syntactic rules and
relations, and lower case letters in stating semantic relations; we will find
ourselves using both when we want to say "To express such-and-such meanings,
use such-and-such forms".
Often practical considerations complicate the definition of a programming
language. For example, computation is done only with numbers up to a certain
size; computations which are intended to give results larger than the allowed
size give erroneous results or stop the program. For example, the rule that
If E is E *E , then a = a xa
1 2 1 2
is only valid if a xa is within the allowed range of sizes for numbers.
1 2
Such pragmatic considerations complicate definitions, and can be forgotten
most of the time in elementary programming.
We may now give more precise and complete definitions of the aspects of
SAIL which have already been introduced.
# A printing command has the form
PRINT(O ,O ,...,O ) PRINT(O );
1 2 n 1
PRINT(O );
2
.
.
.
PRINT(O )
n
with n >= 1 . Each operand O is either an expression whose value is a
i
number, or a message in quotation marks, or NEWLINE. If not enough room is
left on a line for the value of a numerical expression, it will automatically
begin a new line.
# A numerical expression, if it is not a constant or a variable, has one of
the forms given below in the left column, where the corresponding vaue is shown
in the right column.
%form% %value%
E +E a +a
1 2 1 2
E -E a -a
1 2 1 2
+E a
-E -a
E *E a xa
1 2 1 2
E /E a /a (undefined if a = 0)
1 2 1 2 2
a
2
E **E a
1 2 1
ABS(E) abs(a)
(E) a
SIN(E) sin(a) , a in radians
COS(E) cos(a) , a in radians
LOG(E) log (a) , a > 0
e
a
EXP(E) e
SQRT(E) square root(a) , a >= 0
-1
ATAN(E) tan (a) , in range (-pi/2 , pi/2)
A string expression is any sequence of symbols enclosed in (double) quotation
marks. (Still other forms of expression will be described later.)
In the table above, the right-hand column lists a number of operations
such as multiplication and finding square roots, which occur frequently in
computation and are therefore made available as %primitives% (operations which
do not have to be programmed from simpler operations and commands) in SAIL.
Some of them, such as the arithmetic operations, are primitives of the computer
language into which SAIL programs are translated. Others, such as the square
root operation, are not computer language primitives; the translator
automatically includes a short computer language program to perform them, if
they are used in a SAIL program. The left-hand column shows the way that these
operations are written in SAIL. Sometimes, as with addition and the sin
function, the SAIL notation for the function is the familiar way of writing
the operation, but in other cases, such as multiplication and square root, the
limitations of computing equipment (especially the keyboard) force the use of
an unfamiliar notation. We will tend to use lower case letters (log ) when
e
talking about the operation itself (semantics), and capital letters (LOG)
when talking about the way it is expressed in SAIL (syntax).
# A block (B) is a command of the form
BEGIN D ; D ; ...; D ; C ; C ; ...; C END
1 2 m 1 2 n
To execute a block, one executes the commands in the order written. Variables
declared in a block may only be referred to in that block. A program is a
block.
# An identifier (I) is a sequence of letters and/or digits, starting with
a letter. Identifiers, thus far, have been introduced only as names of
variables.
The identifiers are
A,B,C,...,X,Y,Z,AA,AB,...,AZ,A0,A1,...,A9,
BA,...,B9,...,ZA,...,Z9,AAA,...,
EXAMPLE,...,EX12A83,...,YETLONGEREXAMPLE,...
VERYMUCHLONGEREXAMPLEWHICHYOUWOULDQUICKLYTIREOFWRITINGOFTEN,...
Words which have a fixed meaning in SAIL, such as BEGIN, FOR, STEP, UNTIL,
and END, may not be used as identifiers. The SAIL Manual, page 151, contains
a list of these %reserved% words.
%Spacing%.
In the preparation of a program, one may freely use blank spaces, or even
entire blank lines. Like the use of paragraphs, margins and punctuation in
English writing, this is an art of some importance in maintaining
intelligibility. Some ways to use spacing effectively will be discussed
later. For the present, we need only say that spaces may not be inserted into a
number, word, or variable, and that if a number, reserved word, or variable is
immediately followed by another of these, there must be at least one space
between them. Thus one must not write
FORI:=ASTEP1UNTIL100DOPRINT(I,1/I)
but rather
FOR I:=A STEP 1 UNTIL 100 DO PRINT(I,1/I)
where only the necessary spaces have been inserted. The end of a line counts
as a space. (This fact limits identifiers to about 80 characters.) In
general, if a program is legible, the use of spaces is probably correct.
Commas are not permiteed as punctuation within a number; one must not write
1,234,567.890
but rather
1234567.890
Exercise: What does the program
PRINT(1,234,567.890)
do?
%Printing Format%.
When results of a program are printed, the line printer is made ready
to print the first line of a new page. A page has room for 66 lines, each
of 132 characters. Lines are 1/6 of an inch apart, and the characters on
a line are 1/10 of an inch apart, center to center. Printing of a numerical
value normally requires thirteen characters. Thus as many as ten numbers are
printed on a line. If too much information is printed to appear on one line
it wraps around the next line on the terminal; it is omitted on the line
printer (the earlier section on the PRINT command is in error about this).
The terminal screen is 24 characters high and 80 wide.
Very large or very small numbers are printed in an unfamiliar way in
order to fit in thirteen characters. The number 483000000000000.
15
(15 digits) is printed as .4830000@15 , meaning .483 x 10 , or .483
multiplied by ten fifteen times. The number 0.0000000000628753 (first
significant digit in the eleventh decimal place) is printed as
-10
.6287530 @ -10 , meaning .628753 x 10 , or .628753 divided by ten
ten times. In general, b @ a , where a is an integer, is printed to
a
mean b x 10 when the number would othrwise not fit the available space.
The first character is always a blank or minus sign; the next eight are seven
digits and a decimal point; the last four are blank or contain the power of 10.
Integers (exressions written without division or decimal points, roughly) are
printed right justified in thirteen spaces, for example as
-12345
In a printing command, the operands may be expressions, but may also be
any of the following:
NEWLINE goes to the start of the next line;
FORMFEED goes to the start of a new page. (This feature
is not recommended until you have more experience in
programming; errors in programming may use up an expensive
amount of paper).
TAB fills out the line with blanks to (but not including) the
next tabulator stop; there is a tab stop after every eight
character positions.
SPACE prints one blank space; equivalent to " ".
BELL rings a bell or makes some other sound, if printed at a
terminal.
%Example%.
PRINT(SPACE,13.5,"ABC",TAB,2/3)
13.50000 ABC .6666667
( )( )( )( )
000000000111111111122222222233333333
123456789012345678901234568901234567
Here we have put parentheses under the symbols printed for each operand. The
last two lines, read vertically, give the column numbers.
%String Constants%.
In addition to numerical values, we have seen that one may print values
which are sequences of symbols, or %characters%. Such values are called
%strings%; words, and decimal representations of numbers, are particular kinds
of strings. The constant representing a particular string is written by
enclosing the string between double quote marks. Since the arithmetical
operators and functions with which we are as yet acquainted are obviously not
applicable to strings, the only use which we can as yet make of strings is to
print them. For example, the program:
PRINT(1.5,"1.5",2*3,"2*3",NEWLINE)
PRINT("ABCDEF+-*/1234","NEWLINE")
causes the printing of the following lines:
1.500000 1.5 6.000000 2*3
ABCDEF+-*/1234NEWLINE
A quoted string constant should be written on a single line of the program.
Longer string constants can be written by juxtaposing two or more quoted
string constants, with an ampersand between them:
PRINT("ABCDEFGHIJKLM" PRINT("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
& "NOPQRSTUVWXYZ")
When writing a program using string constants which contain blanks, it
is customary to use a lower case "b" to stand for a blank, and then to type
the "b" as a blank. For example, to make a program print
*
* *
* *
one would write the program
PRINT("bb*",NEWLINE,"b*b*",NEWLINE,"*bbb*")
and then type it at the terminal keyboard
PRINT(" *",NEWLINE," * *",NEWLINE,"* *")
%Example%.
To print the square like that shown below, in a larger size, say eight
inches on a side,
**********
* *
* *
* *
* *
**********
we could write the program
FOR I:=1 STEP 1 UNTIL 80 DO
PRINT("*");
PRINT(NEWLINE);
FOR I:=1 STEP 1 UNTIL 46 DO
BEGIN
PRINT("*");
FOR J:=1 STEP 1 UNTIL 78 DO
PRINT("b");
PRINT("*",NEWLINE)
END;
FOR I:=1 STEP 1 UNTIL 80 DO
PRINT("*")
%Exercise%. Write a program to print the triangle of asterisks shown below:
**
****
******
********
**********
************
**************
except that your triangle should be larger; it should be 60 characters high
and 120 characters wide.
%Problem Decomposition%.
Let us consider the problem of printing a small table of natural
logarithms of the number from 10 to 99. Envision the general appearance of
the table as
TABLE OF LOGARITHMS
0 1 2 3 4
10 log 10 log 11 ... log 14
15 log 15 log 16 ... log 19
20 log 20
25 log 25
30 log 30
.
.
.
95 log 95 log 99
If we had available a fantastically rich and expressive programming
language, we might write in it simply
WRITE A TABLE OF LOGARITHMS WITH HEADINGS ..., etc.
As we do not, we must repeatedly decompose the task into sequences, and
iterations, of simpler tasks, until we have reduced it to tasks each of which
can be carried out by a single command in SAIL.
We begin by observing that the first two lines of the table, being a title
and heading, are completely different in structure from the rest. Because the
printing mechanism prints one line after another, we may decompose our task
into the following "program":
BEGIN
(declarations)
Print the title;
Print the heading;
Print the body of the table
END
These are not SAIL commands, nor do they completely define the particular
table we want, so that the program is not yet executable by a computer.
However, if we can find commands to do the three parts of the task, we can
put them together in such a block to do the entire task. We can express
Print the title
in SAIL as
PRINT(TAB,TAB,TAB,TAB,TAB,"TABLE OF LOGARITHMS",NEWLINE,NEWLINE)
We observe that the heading consists of two qualitatively distinct parts:
a blank region above the 10, and then a series of numbers. Thus we decompose
Print the heading.
into
PRINT(TAB);
FOR I:=0 STEP 1 UNTIL 4 DO PRINT(I);
PRINT(NEWLINE,NEWLINE)
Looking at the body of the table, we see that it consists of eighteen
lines, which must be printed in sequence, and whose differences from each other
can be characterized by their numerical dependence on a variable. This is a
natural situation for decomposition, into an iteration of one command which can
print any line of the table body. Thus
Print the body of the table
reduces to
iterate the following, with a = 10,15,...,95;
write a line of the form
a,log(a),log(a+1),...,log(a+4)
Now the program has become much less abstract; it has been decomposed into the
following structure:
BEGIN
(declarations)
PRINT(TAB,TAB,TAB,TAB,TAB,"TABLE OF LOGARITHMS",NEWLINE,NEWLINE);
PRINT(TAB);
FOR I:=0 STEP 1 UNTIL 4 DO PRINT(I);
PRINT(NEWLINE,NEWLINE);
Iterate the following, with A = 10,15,...,95:
(Write a line of the form
A log(A) log(A+1) ... log(A+4))
We may decompose
Write a line of the form
A log(A) log(A+1) ... log(A+4)
into
BEGIN
PRINT(A);
Write log(A) log(A+1) ... log(A+4);
PRINT(NEWLINE)
END
and further decompose the third line above into
FOR C:=0 STEP 1 UNTIL 4 DO
PRINT(LOG(A+C))
or into
FOR C:=A STEP 1 UNTIL A+4 DO
PRINT(LOG(C))
Combining these pieces, we get this complete program:
BEGIN
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
INTEGER I,A,C;
SETPRINT("LOG.OUT","B");
SETFORMAT(13,7);
PRINT(TAB,TAB,TAB,TAB,TAB,"TABLE OF LOGARITHMS",NEWLINE,NEWLINE);
PRINT(TAB);
FOR I:=0 STEP 1 UNTIL 4 DO PRINT(I);
PRINT(NEWLINE,NEWLINE);
FOR A:=10 STEP 5 UNTIL 95 DO
BEGIN
PRINT(A," ");
FOR C:=0 STEP 1 UNTIL 4 DO
PRINT(LOG(A+C));
PRINT(NEWLINE)
END
END
which when executed, prints the following:
TABLE OF LOGARITHMS
0 1 2 3 4
10 2.302585 2.397895 2.484907 2.564949 2.639057
15 2.708050 2.772589 2.833213 2.890372 2.944439
20 2.995732 3.044522 3.091042 3.135494 3.178054
25 3.218876 3.258097 3.295837 3.332205 3.367296
30 3.401197 3.433987 3.465736 3.496508 3.526361
35 3.555348 3.583519 3.610918 3.637586 3.663562
40 3.688879 3.713572 3.737670 3.761200 3.784190
45 3.806663 3.828641 3.850148 3.871201 3.891820
50 3.912023 3.931826 3.951244 3.970292 3.988984
55 4.007333 4.025352 4.043051 4.060443 4.077537
60 4.094345 4.110874 4.127134 4.143135 4.158883
65 4.174387 4.189655 4.204693 4.219508 4.234107
70 4.248495 4.262680 4.276666 4.290460 4.304065
75 4.317488 4.330733 4.343805 4.356709 4.369448
80 4.382027 4.394449 4.406719 4.418841 4.430817
85 4.442651 4.454347 4.465908 4.477337 4.488636
90 4.499810 4.510860 4.521789 4.532599 4.543295
95 4.553877 4.564348 4.574711 4.584968 4.595120
The general principles of decomposition we have used, so far, are these:
(1) If a task can be carried out by a single SAIL command, use that command.
(2) If a task can be carried out by a short sequence of dissimilar processes,
decompose it into a sequence of commands to perform those processes. If
that sequence must be iterated, or otherwise referred to as a whole, make
a block of it.
(3) If a task can be carried out by a sequence of similar processes, where the
length of the sequence can be predetermined, decompose it into an iteration
of a command which represents the typical process of the sequence, using
the iteration variable or expressions containing it to represent those
aspects of the processes which differ.
For example, to print the numbers 0,.01,.03,.06,.10,.15,...,.78,.91
(the principle which generates the above sequence is that the numbers
differ by successive steps of .0l,.02,.03,.04,...,.13 ) we first find
a general formula for the i-th number. There are i-1 graduated steps
from the first number to the i-th; the first step is .01 , the last is
.01(i-1) , so the average step is .005 x i , and the i-th number is
.005 x i x (i-1) . We can now program the printing as
FOR I:=1 STEP 1 UNTIL 14 DO
PRINT(.005*I*(I-1))
(The following section provides methods of design, for iterative programs,
which would allow programming of this problem even if we were unable to
find the general formula for the i-th number, using instead the principle
which generates the sequence.)
The decomposition method of program design is a powerful intellectual
tool, but it is not an automatic problem solver. It will not salvage a
fundamentally wrong approach to a problem, nor will it of itself create insight
into the possible methods of attacking a problem. Experienced programmers
draw on a large number of frequently useful methods; reading many programs is
the only way to acquire this experience.
%Exercise%. Write a program to print a larger version of the diamond-shaped
pattern shown below:
*
***
*****
*******
*********
*******
*****
***
*
Your diamond, however, should be 59 symbols high, and 59 wide.
%Exercise%. As above, but with two diamonds side by side:
* *
*** ***
***** *****
**************
***** *****
*** ***
* *
%Exercise%. Print the number sequence
20
1,2,3,4,5,6,7,8,9,10,20,30,40,...,90,100,200,...1000,...,10
Solutions, omitting declarations, etc.:
(1) FOR J:=1 STEP 1 UNTIL 30 DO
BEGIN COMMENT LINE OF 30-I SPACES, 2*I-1 STARS.;
FOR J:=1 STEP 1 UNTIL 30-I DO
PRINT(" ");
FOR K:=1 STEP 1 UNTIL 2*I-1 DO
PRINT("*");
PRINT(NEWLINE)
END;
FOR I:=29 STEP -1 UNTIL 1 DO
BEGIN COMMENT LINES AS ABOVE, IN REVERSE ORDER;
FOR J:=1 STEP 1 UNTIL 30-I DO
PRINT(" ");
FOR K:=1 STEP 1 UNTIL 2*I-1 DO
PRINT("*");
PRINT(NEWLINE)
END
or
FOR I:=-29 STEP 1 UNTIL 29 DO
BEGIN
FOR J:=1 STEP 1 UNTIL ABS I DO
PRINT("b");
FOR K:=1 STEP 1 UNTIL 59-2*(ABS I) DO
PRINT("*");
PRINT(NEWLINE)
END
(2) FOR I:=-29 STEP 1 UNTIL 29 DO
BEGIN
FOR L:=1 STEP 1 UNTIL 2 DO
BEGIN
FOR J:=1 STEP 1 UNTIL ABS I DO
PRINT("b");
FOR K:=1 STEP 1 UNTIL 59-2*(ABS I) DO
PRINT("*");
FOR J:=1 STEP 1 UNTIL ABS I DO
PRINT("b")
END;
PRINT(NEWLINE)
END
(3) FOR POWER:=0 STEP 1 UNTIL 19 DO
FOR M:=1 STEP 1 UNTIL 9 DO
PRINT(M*10**POWER);
PRINT(10**20)
%Comments in Programs%.
A computer program embodies the intent of its author, but, if it is not
accompanied by an explanation, it may be unclear to anyone else. It may even
be unintelligible to its author himself after some lapse of time. It is
permitted in SAIL to insert comments anywhere in a program (except in quoted
string constants) by writing the word COMMENT; what follows, up to and
including the next semicolon, has no effect on the meaning of the program,
and serves only as a comment. When decomposing a problem, the early stages
of a decomposition can and should be kept as comments. For example, the log
table program might have been written
BEGIN
COMMENT PROGRAM FOR TABLE LOG(10) TO LOG(99);
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
INTEGER I,A,C;
SETPRINT("LOG.OUT","B");
SETFORMAT(13,7);
COMMENT PRINT THE TITLE;
PRINT(TAB,TAB,TAB,TAB,TAB,"TABLE OF LOGARITHMS",NEWLINE,NEWLINE);
COMMENT PRINT THE COLUMN HEADINGS;
PRINT(TAB);
COMMENT NO HEADING OVER COLUMN CONTAINING A;
FOR I:=0 STEP 1 UNTIL 4 DO PRINT(I);
PRINT(NEWLINE,NEWLINE);
COMMENT PRINT THE BODY OF THE TABLE;
FOR A:=10 STEP 5 UNTIL 95 DO
COMMENT LINE WITH A,LOG(A),...,LOG(A+4);
BEGIN
PRINT(A," ");
FOR C:=0 STEP 1 UNTIL 4 DO
PRINT(LOG(A+C));
PRINT(NEWLINE)
END
END COMMENT END OF A-ITERATION;
%Programming Superstitions%.
A novice programmer writes a program, runs it, and finds that it doesn't
work. That is, it gives him results different from what he had expected. He
experiments at random with a variety of changes, some of which affect the
program to give the desired result. He generalizes from this, and thereafter
says that a programer must do such-and-such to get correct results. Example 1
was written by a programmer who wanted to sum the first 100 reciprocals and
print the results. He found that the program printed zero, one hundred times.
He decided that because of the PRINT(S) line in the program, it was printing
S every time an assignment was made to S . So he put a command which
printed a blank just before the assignment to S , thinking that that might
tell the translator that he did not want S to be printed then. The result was
Example 2. He ran it. It printed the correct answer. He was now convinced
that, if you ever print a variable in the program, it will be printed every time
it is changed unless it is preceded by a PRINT command which does not mention
that variable.
%Example 1%. %Example 2%.
BEGIN BEGIN
(declarations, etc.) (declarations, etc.)
S:=0; S:=0;
FOR I:=1 STEP 1 UNTIL 100 DO FOR I:=1 STEP 1 UNTIL 100 DO
COMMENT S IS SUM OF 1, 1/2,1/3, ETC. COMMENT S IS SUM OF 1, 1/2, 1/3, ETC.
S:=S+1/I; PRINT(" ");
PRINT(S) S:=S+1/I;
END PRINT(S)
END
Our programmer now has a superstition. Like most superstitions, it is
based on observation and experiment. Like most superstitions, more controlled
experimentation would make this one untenable. For example, omitting the
COMMENT line from Example 1 would make it run correctly, contrary to the
superstition. What is actually wrong with Example 1 is that the programmer
failed to terminate his COMMENT line with a semicolon. The result is that the
next line is treated as part of the COMMENT, and is ignored. The command
which is iterated is therefore the PRINT command. When the programmer
introduced an extra PRINT command to print a blank, it became part of the
COMMENT in Example 2, and the assignment to S , no longer being part of the
COMMENT, was iterated. The semicolon which followed it marked the end of the
iterative command, so the PRINT(S) command was only done once.
The programer's random experimentation was doomed to failure. Trial and
error virtually never succeeds in making a program correct. Experimentation
must be guided by application of general rules and theory. The programmer
could have reasoned in this way about Example 1:
(1) Because 100 numbers were printed, a PRINT command must have been iterated.
(2) The only PRINT command is the PRINT(S) command. It must have been
iterated by the clause which begins FOR I .
(3) This appears inconsistent with the definition of iterative commands,
because there is a semicolon in the line just before the PRINT, yet the
semicolon is not a legitimate part of the assignment, the PRINT, or of an
iterative command.
(4) This suggests examining why the semicolon was not detected as
ungrammatical. We know of two ways semicolons can appear in programs.
One is separating commands in a block, but if this semicolon was serving
that function, the iteration and the PRINT would have occupied different
commands in the block and the PRINT would not have been iterated. The
semicolon must therefore be serving its other function which is to
terminate a comment. We now inspect the definition of a comment and the
error becomes obvious.
The novice programmer will often find the behavior of his program
difficult to diagnose. Experimentation may be helpful in leading him to
discover where he misinterpreted the rules and definitions of the language.
He should however be extremely cautious about deciding that the real rules
of the language are different from those he has been told. Almost invariably
this decision would be wrong. He would do better to take his difficulty to a
member of the teaching staff or to an experienced SAIL programmer.
%Program Variables and Assignment%.
1 5 1
The harmonic numbers 1 , 1 - , 1 - , 2 -- , etc., are defined by
2 6 12
n
1 1 1 1 1
H = - . (This is mathematical shorthand for - + - + - + ... + - .)
n i 1 2 3 n
i=1
Evaluation of this series seems to be a natural candidate for iteration,
decomposing the problem
print the first 100 harmonic numbers
into
FOR I:=1 STEP 1 UNTIL 100 DO
print the I-th harmonic number
However, here we are stuck even if we realize that H = H + 1/I , and
I I-1
that we have just printed H at the time we want H (I >= 2) . Let
I-1 I
us, however, go as far as we can, making a special case of H .
1
Print H
1
FOR I:=1 STEP 1 UNTIL 100 DO
Print (1/I) + (the number most recently printed)
What is needed here is a mechanism for saving the results of previous
computations. For this purpose, SAIL provides the ability to use variables
which hold the values resulting from previous computations. They are not
analogous to the variables of mathematics, where a variable denotes a single,
unknown value, which does not "vary" at all, nor to the iteration variables,
which run through a preordained set of values. We shall call them
%program variables%, and a program may change their values whenever desired.
We shall use upper case letters for program variables and lower case letters
for mathematical variables.
We modify the above program by using a variable, S (called that to
remind us that it is a sum), whose value will be changed as needed to remain
equal to the number most recently printed. We use comments extensively to
explain the significance of the information kept as the value of a variable.
SAIL requires that each program variable used be explicitly created by
a special kind of command called a %declaration%. The declaration
REAL S
creates a variable S which is permitted to take any number as its value.
("Real" is used here in the sense, "not imaginary". What mathematicians
call real numbers are what the rest of us call numbers.) We might also have
occasion to declare
INTEGER A
to create a variable A which could take on only whole-number values,
whether positive, negative, or zero. (There are pragmatic reasons for having
several types of program variables; the more restricted types, such as the
integer variables, typically require less of the computer's memory resources
for their representation, and the operations of arithmetic can often be
performed on them more rapidly.)
In a program, a command which, when executed, gives the program variable
I the value a of the expression E , is written
I:=E
which can be read "assign the value of the expression E to the variable I ",
or simply "Set I equal to E ". Such a command is called an %assignment%.
Our program, as modified, now becomes
BEGIN
COMMENT THE N-TH HARMONIC NUMBER H(N) = 1 + 1/2 + 1/3 + ... + 1/N;
Create a variable S;
COMMENT S WILL TAKE ON THE VALUES OF THE HARMONIC NUMBERS
H(1),...,H(100);
Give S the value 1 (= H ) and print H ;
1 1
FOR I:=2 STEP 1 UNTIL 100 DO
COMMENT S = H(I-1);
(Take (1/I) + the old value of S (= H ) as the new value for S
I-1
(= H ) and print S.)
I
END
We decompose
give S the value 1 and print H ;
1
into
S:=1;
PRINT(S)
and we change
take (1/I) + the old value of S (= H ) as the new value for S
I-1
(= H ) and print S
I
to
BEGIN
S := 1/I + S
PRINT(S)
END
Our program is now
REAL S;
S:=1;
PRINT(S);
FOR I:=2 STEP 1 UNTIL 100 DO
BEGIN
S := 1/I + S;
PRINT(S)
END
The general form of declarations which create program variables is
T I ,I ,...,I
1 2 n
where T is the %type% of value which the variables I ,I ,..,I (n >= 1)
1 2 n
take on. In addition to the types INTEGER and REAL, we shall encounter others.
The reader should assume for the moment that all declarations must be
written at the beginning of the program.
%Reading%.
The programs we have seen until now have each been capable of only a
single computation. To enable a program to solve a different problem each time
it is used, we have to provide it with different information each time it is
run. This information can be obtained from the program's user at his terminal.
When the program needs information, it prints out a dash on the terminal, and
waits for the user to type the desired information, followed by a RETURN. It
then automatically continues with the calculation, until more information is
needed from the user.
To get a number from the user, we use the expression READ. The system
will obtain a number, as above, and use that as the (momentary) value of the
expression READ. For example, the program
BEGIN
(declarations, etc.)
PRINT(SQRT(READ))
END
will get a number from the user and print out its square root. If the user
types 2 , followed by a RETURN, the program prints 1.414214 .
Usually, a program will need several pieces of information from the user.
It is usually advisable for the program to print a request for each, before
executing a command containing READ. (This is called %prompting% the user.)
A program to get two numbers, printing the square root of the first and the
square of the second, might be
BEGIN
(declarations)
PRINT("SQUARE ROOT OF");
PRINT(SQRT(READ),NEWLINE);
PRINT("SQUARE OF");
PRINT(READ**2)
END
When this program is executed, the results printed at the terminal might be
SQUARE ROOT OF - 2
1.414214
SQUARE OF - 11
121
where the user typed the 2 and 11 , the rest being printed by the program.
If the results are also printed on the line printer, the part typed by the user
would not be present; the listing would be something like
SQUARE ROOT OF 1.414214
SQUARE OF 121
Because of this, and because most input data are needed more than once by a
program, it is usually advisable to assign to a variable the number typed by
the user.
BEGIN
(declarations)
PRINT("SQUARE ROOT OF");
FIRST:=READ;
PRINT(FIRST,"TO SQUARE ROOT OF");
LAST:=READ;
PRINT(LAST,NEWLINE,NEWLINE);
FOR I:=FIRST STEP 1 UNTIL LAST DO
PRINT(I,SQRT(I),NEWLINE)
END
If the user types 2 and 5 at the appropriate times, the results
printed at the terminal would be
SQUARE ROOT OF - 2
2 TO SQUARE ROOT OF - 5
5
2 1.414214
3 1.732051
4 2.000000
5 2.236068
while the results printed on the paper listing would be
SQUARE ROOT OF 2 TO SQUARE ROOT OF 5
2 1.414214
3 1.732051
4 2.000000
5 2.236068
%Rule of good programming practice%:
All input data should appear in the printed output. This is done to protect
against the possibility that the user made a typing error. Such a repetition
of input in the output is called an %echo%.
%Exercise%. Write a program which prints a rectangle after reading its
height and width. Use prompting and echoes.
%Exercise%. Write a program to add a series of numbers from the terminal,
printing the cumulative sums. The set of numbers to be added should be
preceded by a number giving the size of the set. Use prompting and echoes.
%Conditional Commands%.
SAIL offers a type of command which tests whether some condition is true
or false, and executes one command or another accordingly. The general form
of such commands is
IF E THEN C ELSE C
1 2
or
IF E THEN C
1
where E is a condition which can be tested. If E is true, C is
1
executed; if E is false, C is executed in the first case, and nothing is
done in the second.
The conditions may be of any of the forms
E = E
1 2
E NOT = E or E NEQ E (meaning E not equal to E )
1 2 1 2 1 2
E < E
1 2
E <= E or E LEQ E (meaning E less than or equal to E )
1 2 1 2 1 2
E > E
1 2
E >= E or E GEQ E (meaning E greater than or equal to E )
1 2 1 2 1 2
Expressions such as these, having as values TRUE or FALSE rather than a number,
are called %Boolean expressions% (after logician George Boole).
%Example%.
To print a table of squares, starting a new line after every fifth number,
we keep a variable with which we count how many squares have been printed on
the current line. When the count reaches five, we start a new line and reset
the count to zero.
BEGIN
(declarations)
COUNT:=0;
FOR I:=1 STEP 1 UNTIL 93 DO
BEGIN
PRINT(I*I);
COUNT := COUNT+1
IF COUNT =5 THEN
BEGIN
PRINT(NEWLINE)
COUNT:=0
END
END
END
%Example%.
To print the picture of a square with a blank diagonal as shown below
****
* ***
** **
*** *
****
we could write
FOR R:=1 STEP 1 UNTIL 5 DO COMMENT 5 ROWS;
BEGIN
FOR C:=1 STEP 1 UNTIL 5 DO COMMENT 5 CHARACTERS PER ROW;
IF R=C THEN
PRINT("b") COMMENT ON THE DIAGONAL;
ELSE
PRINT("*"); COMMENT NOT ON DIAGONAL;
PRINT(NEWLINE)
END
We could, in this case, have designed the program without conditional commands,
by viewing the pattern as a pair of triangles separated by a blank diagonal
line:
FOR R:=1 STEP 1 UNTIL 5 DO
BEGIN
FOR C:=1 STEP 1 UNTIL R-1 DO
PRINT("*");
PRINT("b");
FOR C:=1 STEP 1 UNTIL 5-R DO
PRINT("*");
PRINT(NEWLINE)
END
%Example%.
In the game of chess, the rook is a piece which can move horizontally or
vertically, as far as desired (unless blocked by another piece). We consider
the problem of drawing a diagram to show the rook at a specified place on the
chessboard, with all the squares to which the rook might move marked with
asterisks. Figure 7 shows such a diagram with the rook in the fourth row and
the third column.
..*.....
..*.....
..*.....
**R*****
..*.....
..*.....
..*.....
..*.....
Figure 7. Chessboard showing possible rook moves from row 4, column 3.
The large number of dots and asterisks suggests using an iteration, but since
they are intermixed there is little hope of writing separate iterations to
print dots and to print asterisks. Instead, we iterate a conditional command
which, when executed, prints one character. It chooses which character to
print in each position of the board by testing whether the position is occupied
or attacked by the rook. The iterative structure of the program is
INTEGER ROOKROW,ROOKCOL;
ROOKROW:=READ;
ROOKCOL:=READ;
FOR R:=1 STEP 1 UNTIL 8 DO COMMENT DRAW THE R-TH ROW;
BEGIN
FOR C:=1 STEP 1 UNTIL 8 DO
Print the correct character for column C of row R;
PRINT(NEWLINE)
END
The printing command must print "R" if r = rookrow and c = rookcol ;
otherwise, it must print "*" on the rook's row (r = rookrow) and on the
rook's column (c = rookcol) , and "." elsewhere. The printing command
needed can be written:
IF R=ROOKROW THEN
COMMENT PRINT ONE CHARACTER ON ROOK'S ROW;
IF C=ROOKCOL THEN PRINT("R")
ELSE PRINT("*")
ELSE COMMENT NOT ON ROOK'S ROW;
IF C=ROOKCOL THEN PRINT("*")
ELSE PRINT(".")
It is essential to the above command that whenever it is executed, it prints
exactly one character. The first condition chooses between two commands; each
of them, if executed, prints one character, as desired. What would happen if
the above printing command were designed so that when R = ROOKROW it would
print the entire 8 character row? (If in doubt, try it.)
Often, when a long series of actions is desired, but the actions are a
mixture of several different kinds, a programmer will write an iterative
command, iterating a conditional command which selects the appropriate action
for each value of the iteration variable.
The grammar of conditional commands permits an apparently ambiguous
situation to arise. Suppose we wanted to write a command to test variables
x and y , printing 2 if x NOT = 0 , printing 1 if x = 0 and y = 0 ,
and doing nothing if x = 0 but y NOT = 0 . We might write:
IF X = 0 THEN
IF Y = 0 THEN PRINT(1)
ELSE PRINT(2)
On the other hand, if we wanted to do nothing if x NOT = 0 , print 1 if
x = 0 and y = 0 , and print 2 if x = 0 and y NOT = 0 , we might write
IF X = 0 THEN
IF Y = 0 THEN PRINT(1)
ELSE PRINT(2)
These are the same command, except for the spacing, which is not semantically
significant. Yet the first supposedly prints 2 if x NOT = 0 , while the
second does not print anything if x NOT = 0 . Which does the command mean?
It has the second meaning; where an ELSE could be matched with more than one
IF, it is matched with the %nearest% possible one. We could force the ELSE to
match the first IF, as we intended in the first program, by "hiding" the second
IF inside a block, thus:
IF X = 0 THEN
BEGIN
IF Y = 0 THEN PRINT(1)
END
ELSE PRINT(2)
As a general rule, between any IF and its matching ELSE, there must be the same
number of IFs as ELSEs, not counting those "hidden" inside blocks.
IF A THEN means IF A THEN
IF B THEN C BEGIN
ELSE D IF B THEN C
ELSE D
END
%Exercise%. In the game of chess, the queen is a piece which can move
horizontally, vertically, or diagonally. Write a program to read, from a
punched card, the position of the queen (the number of the row and the number
of the column) and to print a diagram showing to which squares the queen can
move, as in Figure 8.
..*..*..
*.*.*...
.***....
**Q*****
.***....
*.*.*...
..*..*..
..*...*.
Figure 8. Chessboard showing possible queen moves from row 4, column 3
%Exercise%. Write a program to keep track of a checking account. Let the
initial balance be zero. The first number on the input file is the total
number of checks and deposits. The remaining data are the amounts of checks
(negative) and deposits (positive). For each datum, the program should print
the datum and the balance after processing the datum. Then change the program,
to impose sevice charges of $0.05 per deposit and $0.10 per check.
%Exercise%. Same as above, but waiving service charges on accounts which have
a balance of over $300.00 after the transaction.
%Exercise%. Same as above, but taking into account overdrafts, according to
the following rules:
1. Service charges of $0.05 per deposit, $0.10 per check paid.
2. Penalty of $3.00 per check written against insufficient funds
(overdraft).
3. Checks which would leave a balance less than -$50.00 are not honored.
Warning: It is easy to make a mistake in programming the above policy.
Remember that the program must accept deposits even to overdrawn accounts, and
that the service charge on a check may overdraw the account. Note that there
is no service charge on a check which is not honored. Read the rules %very%
carefully. Try to think like a banker.
%Logical Connectives%.
At times, we want to execute a command only when a combination of
conditions is satisfied. To execute C only when both E and E are true,
1 2
we might write
IF E THEN IF E THEN C
1 2
We may more simply write a conditional command using a condition, E and E ,
1 2
which is only true if both E and E are true:
1 2
IF E AND E THEN C
1 2
Similarly, to execute C when either one of E and E (or both) is true,
1 2
instead of writing
IF E THEN C
1
ELSE IF E THEN C
2
we could use the condition E OR E , which is true if either (or both) of
1 2
E and E is true, to write
1 2
IF E OR E THEN C
1 2
The printing command used in drawing the rook moves on the chessboard in the
previous section could be written:
IF R = ROOKROW AND C = ROOKCOL THEN
PRINT("R")
ELSE IF R = ROOKROW OR C = ROOKCOL THEN
PRINT("*")
ELSE PRINT(".")
Another logical connective is "NOT", meaning "not"; the condition NOT E
is true if E is false, and false if E is true.
In general, if E and E are Boolean expressions (exressions whose
1 2
values are true or false), then
E AND E
1 2
E OR E
1 2
NOT E
1
are also Boolean expressions. The first is true only when a and a are
1 2
both true. The second is false only when a and a are both false. The
1 2
third is true only when a is false. Ambiguities are resolved by applying
1
NOT first, then AND, then OR, just as multiplications are done before
additions, in the absence of parentheses; for example,
A OR NOT B AND C
means
A OR ((NOT B) AND C)
%Example%.
To print the figures illustrated:
*****
* ***
*****
*****
*****
FOR R:=1 STEP 1 UNTIL 5 DO
BEGIN
FOR C:=1 STEP 1 UNTIL 5 DO
IF R=2 AND C=2 THEN
PRINT("b")
ELSE PRINT("*");
PRINT(NEWLINE)
END
*****
* ***
*****
*** *
*****
FOR R:=1 STEP 1 UNTIL 5 DO
BEGIN
FOR C:=1 STEP 1 UNTIL 5 DO
IF (R=2 AND C=2) OR (R=4 AND C=4) THEN
PRINT("b")
ELSE PRINT("*");
PRINT(NEWLINE)
END
*****
* * *
*****
* * *
*****
FOR R:=1 STEP 1 UNTIL 5 DO
BEGIN
FOR C:=1 STEP 1 UNTIL 5 DO
IF (R=2 OR R=4) AND (C=2 OR C=4) THEN
PRINT("b")
ELSE PRINT("*");
PRINT(NEWLINE)
END
%Exercise%. Use logical connectives to write a simpler solution to the
exercise showing the queen on the chessboard.
%Design of Iterative Commands%.
A certain breeder of rabbits begins with one pair of newborn rabbits.
Each pair of rabbits has its first litter (another pair) after two months,
and another litter of two each month thereafter. At the end of two years,
how many pairs of rabbits will the breeder have?
Let us designate by f the number of pairs of rabbits during the j-th
j
month. We can see that the number of pairs at the j-th month, for j > 2 , is
the number at the previous month (f ) , plus the number of newborn pairs,
j-1
which is equal to the number of pairs in existence two months previously
(f ) . In brief,
j-2
f = f + f (j >= 3) .
j j-1 j-2
The sequence determined by the rule that each number after the second is the
sum of the preceding two, is:
f f f f f f f f f f ...
1 2 3 4 5 6 7 8 9 10
1 1 2 3 5 8 13 21 34 55 ...
This is the well-known Fibonacci sequence.
A program to compute the answer to this problem might be stated:
1. Compute and print f , where f = 1 , f = 1 , and in general,
24 1 2
f = f + f .
j j-1 j-2
(Actually, f is the number just before two years elapse; f is
24 25
is the number just after.)
In the absence of any special knowledge which would allow us to get f
24
wihout first computing f , f , f , f , etc., a natural decomposition
1 2 3 4
of the problem would be:
1.1 Compute in turn f ,f ,...,f , where f = 1 , f = 1 , and
1 2 24 1 2
f = f + f .
j j-1 j-2
1.2 Print f .
24
Step 1.1 cannot yet be expressed as an iteration, because f and f
1 2
are determined by different rules than f ,f ,...,f . Thus Step 1.1 must
3 4 24
first be decomposed as
1.1.1 Set f = 1 ;
1
1.1.2 Set f = 1 ;
2
1.1.3 Compute in turn f ,f ,...,f where f = f + f .
3 4 24 i i-2 i-1
Step 1.1.3 now can be expressed iteratively:
1.1.3' FOR I:=3 STEP 1 UNTIL 24 DO
Compute f by the rule f = f + f
i i i-2 i-1
However, until some provision is made for having retained the values of f
i-2
and f from previous computations as the values of program variables,
i-1
the iterated command can not be expressed in SAIL.
Suppose at a certain stage of the iteration, say I = 8 , that A
contains 8 (= f ) and B contains 13 (= f ) . By the command
6 7
C := A+B
we add 8 + 13 = 21 = f , leaving it in C .
8
To make the analogous action happen at stage I = 9 of the iteration,
we must start it off with A = 13 , and B = 21 . So we add two more commands
to the iterated block
A:=B and
B:=C
which, when I=8 , changes A to 13 and then B to 21 , leaving these
variables with the values expected by the next stage of the iteration.
It remains to make A = 1 = f and B = 1 = f before entering the
1 2
iteration. When the iteration is done, C will contain f .
24
We approach such problems by the following procedure:
(1) Identify the needed information.
At the I-th iteration we need f and f to compute f .
I-2 I-1 I
(2) Choose program variables in which the information is to be systematically
kept at the beginning of each iteration:
We will find f in A and f in B .
I-2 I-1
(3) Assuming that the program variables hold the desired information from
previous computations, design the process for a typical iteration.
To compute f , we need f + f , i.e., A+B .
I I-2 I-1
(4) Determine what information must be retained for the next iteration.
At the next iteration, I will have been increased by 1 , so we
must have f = f in A and f = f in B .
(I+1)-2 I-1 (I+1)-1 I
Let us suppose that at the start of a certain iteration the program
variable A contains the number a (= f ) and B contains the number
I-2
b (= f ) . At the beginning of the next itertion (i.e., the end of the
I-1
current one), A must contain f = b , and B must contain
I-1
f = f + f = a+b . Diagrammatically, we have
I I-2 I-1
A B
Initial situation a b
Desired situation b a+b
We now look for a systematic way of changing the initial situation into the
desired situation. Unfortunately the obvious ways of changing the initial
situation into the desired situation fail. If we write
A:=B
the intial situation will be changed to
A B
New situation b b
so that the value of f (= a) has been lost; it is no longer the value of
I-2
any variable, but is still needed to compute f (= a+b) .
I
On the other hand, if we write
B := A+B
we reach
A B
New situation a a+b
and the value of f (= b) has been lost.
I-1
We see that the source of the difficulty is that the old value of A is
needed to compute the desired value of B , and vice versa; whichever of A
and B we change first, we lose the information needed to compute the
desired value for the other. This is why a third program variable C , was
introduced to hold one of the values safe.
A B C
Initial situation a b any value
Situation after C := A+B a b a+b
Situation after A := B b b a+b
Situation after B := C b a+b a+b
Returning to the process of designing the iteration,
(5) Determine what values the program variables must contain at the beginning
of the first execution of the iterated command.
When I = 3 , we must have initially A = f = f = 1 and
I-2 1
B = f = f = 1 . Thus the iteration must be preceded by A:=1
I-1 2
and B:=1 .
(6) Determine what information from the last execution of the iterated command
must be retained for use after the iteration is complete.
When I = 24 , we will end with A = f = f , and
I-2 23
B = C = f = f . The needed information after the iteration is
I 24
f , which will be retained as the value of B without change to the
24
program.
We may now restate the program in SAIL as
INTEGER A,B,C;
A:=1; COMMENT F(1);
B:=1; COMMENT F(2);
FOR I:=3 STEP 1 UNTIL 24 DO
BEGIN COMMENT A = F(I-2), B = F(I-1);
C := A+B; COMMENT C = F(I);
A:=B; COMMENT A = F(I-1);
B:=C; COMMENT B = F(I);
END;
COMMENT B = F(24);
PRINT("F(24)=",B)
%Exercise%. Design a program to compute f ,f ,...,f and print f in
1 2 24 24
which two new elements of the sequence are computed by each execution of the
iterated command. This can be done by a simpler program than the one given
above.
%Exercise%. Design a program to read 100 numbers from cards and print the
two largest.
%Advice%.
When a programming problem is too difficult to cope with conceptually, it
is usually most productive to solve a simplified version of the problem first.
The above exercise, for example, can be simplified to the problem of finding
the largest one of the 100 numbers.
%Constructing Correct Programs%.
Anyone who has written several computer programs knows that it is hard to
write a program of more than ten lines free from errors ("bugs"). Furthermore,
it is dfficult to locate and remove the errors ("debugging") in a disorganized
program; effort invested in systematic design of the program is usually repaid
manyfold during the debugging phase. A simple tool for diagnosis of incorrect
programs is printing the name and value of each program and iteration variable,
whenever it changes. This technique is called tracing; its drawback is that it
is unselective, and often prints too much information.
%Example%.
The rabbit program of the previous section can be traced by adding
commands as follows:
INTEGER A,B,C;
A:=1;
PRINT("A",A);
B:=1
PRINT("B",B,NEWLINE);
FOR I:=3 STEP 1 UNTIL 24 DO
BEGIN
PRINT("I",I);
C := A+B;
A:=B; B:=C;
PRINT("C",C,"A",A,"B",B)
END
PRINT("F(24) =",A)
%Program Format%.
By the appropriate use of indentation, the structure of a program can be
displayed clearly. Programs should be written so that when someone sees an
iterative clause, he can tell at a glance how much of the program is iterated,
and when he sees a conditional clause, he can tell at a glance how much of the
program is skipped when the condition is false. We recommend a form in which
the iterative command is written with the iterative clause on one line, and the
iterated command on one or more subsequent lines, indented by perhaps three
spaces more than the iterative clause, thus:
S:=0;
FOR J:=1 STEP 1 UNTIL N DO
BEGIN
S := S + I**3;
PRINT(I,S)
END
If the iterated command is very simple, it may be written on the same line with
the iterative clause:
FOR I:=1 STEP 1 UNTIL N DO PRINT(1/I)
For conditional commands, we recommend the form
IF E THEN
C
1
ELSE
C
2
where C and C are indented more than the IF and ELSE lines. If C and
1 2 1
and C are very simple, they can be written on the same lines as the
2
conditions:
IF E THEN C
1
ELSE C
2
or even
IF E THEN C ELSE C
1 2
Most of our examples are indented according to these conventions.
The reader will find that when he has to make corrections to his programs
(and he will spend a significant fraction of his programming career doing just
that), he will find it much easier to correct a program written with systematic
use of indentation. For example, to find what the following nonsense program
does:
FOR I:=1 STEP 1 UNTIL 3 DO
BEGIN
PRINT("A");
IF I = 2 THEN
PRINT("B")
ELSE
BEGIN
PRINT("C");
FOR J:=1 STEP 1 UNTIL 2 DO
PRINT("D");
PRINT("E")
END
END;
PRINT("F");
FOR K:=1 STEP 1 UNTIL 4 DO
IF K NEQ 3 THEN
PRINT("G")
one starts with the most indented sections, finding in turn the following
equivalences:
FOR J:=1 STEP 1 UNTIL 2 DO PRINT("DD")
PRINT("D")
BEGIN PRINT("CDDE")
PRINT("C");
FOR J:=1 STEP 1 UNTIL 2 DO
PRINT("D");
PRINT("E")
END
BEGIN IF I = 2 THEN
PRINT("A"); PRINT("AB")
IF I = 2 THEN ELSE
PRINT("B") PRINT("ACDDE")
ELSE
BEGIN
PRINT("C");
FOR J:=1 STEP 1 UNTIL 2 DO
PRINT("D");
PRINT("E")
END
END
The entire program PRINT("ACDDEABCDDEFGGG")
In brief, the indented regions are significant units, which can be analyzed
independently. In programming courses, graders and programming consultants
should insist on systematic use of comments and indentation.
%Scope of Identifiers%.
In constructing complex programs, especially those written by teams of
cooperating programmers, it is important to be able to design separate portions
of the program independently. One would like to be able to design a command to
carry out a particular task arising in a program, and then to use that command
as a "black box"; that is, to forget everything about it except what task it
performs.
To facilitate this, the general form of a block is like that of a program:
BEGIN D ;D ;...;D ;C ;C ;...;C END
1 2 m 1 2 n
containing any number (possibly zero) of declarations, followed by one or more
commands. In fact, a program is just a block. The variables defined by the
declarations in the head of a particular block are intended to be used only
within that block.
Suppose the block B contains a declaration of a program variable, I ,
and makes assigments to that variable, perhaps using it to hold the partial
sums of a series. Then if B occurs in a program where I is also declared
as a program variable somewhere other than in B , it would appear that every
time B was executed, the value of I would be changed by the assignments
made in B ; thus the internal structure of B could not be ignored in
designing the rest of the program. However, the occurrences of I inside B
are considered to be references to a different variable than those outside B .
The general rules are these:
(1) If B is the block containing a declaration of the identifier I , then
I has B has its %scope%. (It is possible that I has more than one
scope in the program.)
(2) The meaning of a program is unchanged, if an identifier I , throughout
one of its scopes, is everywhere replaced by an identifier I' which does
not otherwise appear in the program. We call this the %renaming%
%principle%. By repeated renaming, any program can be changed into one in
which all variables have unique names.
INTEGER I; INTEGER I;
I:=1; I:=1;
BEGIN COMMENT SCOPE STARTS HERE; BEGIN
INTEGER I; INTEGER J;
I:=2; J:=2;
PRINT(I) PRINT(J) PRINT(2)
END; COMMENT SCOPE ENDS HERE; END;
PRINT(I) PRINT(I) PRINT(1)
It is clear that the second program, and therefore also the first, prints first
a "2" and then a "1" ; as desired, the execution of I:=2 does not disturb
the program variable I outside the block. One can say that the first program
has two distinct variables, both called I .
An occurrence of an identifier which lies in a scope of that identifier
is called %bound%; an occurence not in any scope of that identifier is called
%free%. When a block is written to be used as a section of a larger program,
assignments to its bound variables create no disturbance to the variables
outside the block. Thus
BEGIN
INTEGER I;
I:=J;
J:=K;
K:=I
END
if used within a program with variables named I , J , and K , will exchange
the contents of J and K but leave the I of the main program unaffected.
Naturally, it is a programming error for an identifier to appear free in a
block intended as a complete program.
Because assignments to variables bound in a block have no effect on the
values of variables of the same name occurring outside the block; variables
bound in a block are often called %local% variables of the block. On the other
hand, assignment to a free identifier in a block always changes a variable
declared outside the block, since no variable is free in the entire program.
Thus a block may communicate with the rest of the program through the variables
which occur free in the block. Variables appearing free in a block are often
called %global% variables of the block.
%Arrays%.
Suppose we choose to print the values of f ,f ,...,f from the example
1 2 24
of the rabbit breeder in three columns:
f f f
1 9 17
f f f
2 10 18
. . .
. . .
. . .
f f f
8 16 24
We could not complete the printing of the first line until f had been
17
computed. This situation seems to call for having a large number of program
variables to retain the values of at least f ,f ,...,f , until they can be
1 2 16
printed. Just as (by iteration) we can readily construct a large family of
similar commands, we can also construct a large family of similar program
variables, called an %array%. We create for this purpose an array of 24
program variables, by the %array declaration%.
INTEGER ARRAY X[1:24]
which creates the integer variables called X(1),X(2),...,X(24) when the scope
of X is entered. We can modify our previous computation of f ,f ,...,f
1 2 24
so that whenever f is computed, its value is given to X(i) . Then the
i
program becomes:
INTEGER ARRAY X[1:24];
X[1] := 1; COMMENT F(1) = 1;
X[2] := 1; COMMENT F(2) = 1;
COMMENT COMPUTE X[3],X[4],...,X[24];
FOR I:=3 STEP 1 UNTIL 24 DO
COMMENT ALREADY X[1] = F(1),...,X[I-1] = F(I-1);
X[I] := X[I-1] + X[I-2]; COMMENT X[1] = F(1),...,X[I] = F(I);
COMMENT PRINT THE THREE-COLUMN TABLE;
FOR J:=1 STEP 1 UNTIL 8 DO
PRINT(X[J],X[J+8],X[J+16],NEWLINE)
Notice in the last line, for example, that X[J+8] is not a single program
variable, but may be any of eight different program variables depending on the
value of J .
The use of arrays has two benefits. One is the brevity of the
declaration; to create twenty-four variables otherwise would have required a
declaration like
INTEGER X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,
X13,X14,X15,X16,X17,X18,X19,X20,X21,X22,X23,X24;
The other advantage is that the variables created by an array declaration are
related. We may write X[E] , where E is an expression which takes on
different integer values between one and twenty-four at different times, to
refer to different variables at different times. A single command is thereby
able to change the value of any one of the variables in the array as
X[I] := X[I-1] + X[I-2] does, or to use the value of any of the variables, as
the printing command above does.
In an expression like X[I+J] where X is an array name, the expression
I+J in parentheses is called the %subscript%. It is evaluated to find which
variable X[I+J] designates; if I = 3 and J = 8 , X[I+J] designates the
variable X[11] . Strictly speaking, X[I+J] is not a variable, but an
expression designating a variable; however, a loose usage is customary in which
such an expression is called a variable.
Arrays may also be created in which the variables have two or more
subscripts. Suppose we wanted to write a computer program to keep a record of
the frequency of occurrences of digrams (two-letter pairs) in English text.
(In the first sentence of this paragraph, the digram 'AR' occurs twice;
'ZQ' does not occur at all.) We would probably create an array F by a
declaration like
INTEGER ARRAY F[1:26,1:26]
in which the variable F[1,18] would be used to hold a count of the number of
digrams 'AR' , since A is the first and R the eighteenth letter of the
English alphabet. Upon finding in a text a digram consisting of the i-th
letter of the alphabet followed by the j-th, we would execute the command
F[I,J] := F[I,J]+1 to increase the count for that digram.
The general form of an array declaration
INTEGER ARRAY I ,I ,...,I [E :E ,E :E ,...,E :E ]
1 2 n 11 12 21 22 m1 m2
where n >= 1 , m >= 1 , T is any type, and the %array bounds%
E ,E ,...,E are integer-valued expressions. When the scope of an array
11 12 m2
declaration (the smallest enclosing command) is entered, the variables
I [b ,b ,...,b ]
j 1 2 m
are created for each j (1 <= j <= n) and for each combination of integers
b ,b ,...,b which lie in the respective ranges
1 2 m
(a ,a ),(a ,a ),...,(a ,a ) ; that is, for which a <= b <= a
11 12 21 22 m1 m2 k1 k k2
(1 <= k <= m) .
For example,
INTEGER ARRAY X,Y[1:2,-2:0]
creates the arrays of program variables
X[1,-2] X[1,-1] X[1,0]
X[2,-2] X[2,-1] X[2,0]
Y[1,-2] X[1,-1] X[1,0]
Y[2,-2] Y[2,-1] Y[2,0]
%Example%.
To read 100 numbers and print them in reverse order:
INTEGER ARRAY X[1:100]
FOR J:=1 STEP 1 UNTIL 100 DO X[J] := READ;
FOR I:=100 STEP -1 UNTIL 1 DO PRINT(X[I],NEWLINE)
To generalize the last example, suppose we want to read in a number N ,
followed by N other numbers to be printed in reverse order. We must create
an array large enough for all the data, but this is impossible until the value
of N has been read.
Because array bounds are computed when the block is entered which contains
the array declaration, it would be an error to write
INTEGER N;
INTEGER ARRAY A[1:N];
N := READ;
FOR I:=1 STEP 1 UNTIL N DO A[I] := READ;
.
.
.
Thus the array can not be created when the program begins; the scope of the
array must be a block, entered only after N has been read.
INTEGER N;
N := READ;
BEGIN COMMENT SCOPE OF A;
INTEGER ARRAY A[1:N];
FOR I:=N STEP -1 UNTIL 1 DO
PRINT(A[I],NEWLINE)
END COMMENT SCOPE OF A;
%Exercise%. Design a program to read 100 numbers and print them in four
vertical columns.
%Exercise%. Design a program to read 100 numbers, and print the mean
(average), and the average deviation from the mean, of the numbers. (The
deviation of a number X from the mean M is defined as ABS(X-M) , the
absolute value of the difference between the number and the mean; if the
numbers were 2 , 5 , and 7 , the mean would be 14/3 , and the average
deviation from the mean would be 16/9 .)
%Definitions in SAIL%.
To abbreviate frequently occurring parts of your program, include the
declaration
REQUIRE "{}{}" DELIMITERS;
somewhere %after% the line
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
(because the SAILIO file uses different delimiters). The declaration says that
curly brackets {} will be used to enclose definitions. Thereafter, one or
more lines of the form
DEFINE I = {anything you like};
will act like a comment, except that for the remainder of the program, whenever
you use the identifier I , the translator will treat it as if you had instead
written what was between the brackets. (Warning: if you make grammatical
errors in the definition, they will cause trouble only in the lines which use
that definition.)
%Example%. The following pair of programs are equivalent:
REQUIRE "{}{}" DELIMITERS;
DEFINE UPTO = {:=1 STEP 1 UNTIL };
DEFINE STARS = {"**********"};
FOR I UPTO 10 DO FOR I:=1 STEP 1 UNTIL 10 DO
PRINT(STARS) PRINT("**********")
If you want to use a definition in which some parts are variable, give
names to the places where you want to change the definition each time you use
it. The definition is now written
DEFINE I (I ,I ,...,I ) = {anything};
0 1 2 n
where I , I , etc., are %parameter% names used within the brackets {} for
1 2
places where you want material substituted into the definition. Thereafter in
the program, you can write
I ({A },{A },...,{A })
0 1 2 n
where the %argument% A is any piece of text, to abbreviate the bracketed
i
part of the definition, with the text A replacing the name I wherever it
j j
occurs.
%Example%.
BEGIN
declarations;
REQUIRE "{}{}" DELIMITERS;
DEFINE LOTSOF(WHAT) = {FOR I:=1 STEP 1 UNTIL 10 DO PRINT(WHAT)};
LOTSOF({"A"});
PRINT(NEWLINE);
LOTSOF({I*I})
END
is equivalent to
BEGIN
declarations;
FOR I:=1 STEP 1 UNTIL 10 DO
PRINT("A");
PRINT(NEWLINE);
FOR I:=1 STEP 1 UNTIL 10 DO
PRINT(I*I)
END
The SAIL translator appears not to require the curly brackets around the
arguments, so long as they do not themselves contain commas or curly brackets.
In the last example, one can apparently safely write
LOTSOF("A")
instead of
LOTSOF({"A"})
We make no guarantees, however.
%Standard Preambles in SAIL".
If you would like to include a standard piece of program, like
REQUIRE "SYS:SAILIO.SAI";
INTEGER I,J,K;
REQUIRE "{}{}" DELIMITERS;
DEFINE UPTO = {:=1 STEP 1 UNTIL };
SETPRINT("FRESH.OUT","B");
SETFORMAT(13,7);
in most of your programs, you can save it on a file, say called PREAMB.SAI, and
write, at the place where you want it in your SAIL program (in this case, as the
last declaration), the line:
REQUIRE "PREAMB.SAI" SOURCE!FILE;
This line will be replaced by the source language (i.e., SAIL) file named in
quotes, just as if you had typed in all six lines of the file here. Now
BEGIN
REQUIRE "PREAMB.SAI" SOURCE!FILE;
FOR I UPTO 100 DO
PRINT(I,SQRT(I),NEWLINE)
END
is a complete program, which otherwise would have been several lines longer.
Your instructor may suggest a standard preamble for your use; it may get more
elaborate as time goes on.
%SAIL Output to Files%.
The SETPRINT command in SAIL is used for three purposes: (1) To open and
close files, (2) To switch on and off the flow of output to a file, and
(3) To switch on and off the flow of output to the terminal screen. The
general form of a SETPRINT command is
SETPRINT(f,m)
where f is a file name, in quotes, or NULL, and m is a code calling for
certain combinations of the operations listed above. The operations done by
each code are as follows.
OPEN OR TURN OUTPUT FLOW TURN OUTPUT FLOW
CODE CLOSE FILE TO FILE ON/OFF TO TERMINAL ON/OFF
"B" OPEN ON ON
"F" OPEN ON OFF
"O" OPEN OFF ON
"S" OPEN OFF OFF
"C" NO CHANGE NO CHANGE ON
"I" NO CHANGE NO CHANGE OFF
"T" CLOSE OFF ON
"N" CLOSE OFF OFF
Files are opened before sending output to them, and are not closed until
the output to them is completed; ordinarily, this is done automatically by the
ending of the program. Students will usually not use "T" or "N" . If a
file is already open, the other codes will leave it open and continue to use it
as the output file.
Ordinarily, SETPRINT(f,"B") is used at the start of a program to open an
output file named f , and to establish the flow of output to both file and
terminal. To turn terminal output off, print something in the file only, and
turn the terminal back on, one would write
SETPRINT(NULL,"I"); PRINT(whatever); SETPRINT(NULL,"C")
To turn file output off, print something on the terminal only, and turn file
output back on, one would write
SETPRINT(NULL,"O"); PRINT(whatever); SETPRINT(NULL,"B")
Other codes are little used.
If SETPRINT(NULL,"B") is used at the beginning of the program, the
program will prompt the user at the terminal for the name of an output file.
If your program is named PROG.SAI , give it the output file name PROG.OUT .
This procedure is more error-prone than including the output file name in the
SETPRINT command itself.
%Example preamble using SETPRINT%:
COMMENT ROBERT W FLOYD, OCT 21 77;
REQUIRE "SYS:SAILIO.SAI" SOURCE!FILE;
REQUIRE "{}{}" DELIMITERS;
DEFINE UPTO = {:=1 STEP 1 UNTIL };
DEFINE PROMPTREADECHO(MSG,VAR)=
{BEGIN
PRINT(MSG);
VAR:=READ;
SETPRINT(NULL,"I");
PRINT(VAR,NEWLINE);
SETPRINT(NULL,"C")
END};
DEFINE PROMPTREADCHECKECHO(MSG,VAR,BAD)=
{BEGIN
PRINT(MSG);
VAR:=READ;
SETPRINT(NULL,"O");
WHILE BAD DO
BEGIN
PRINT("INCORRECT INPUT",NEWLINE,MSG);
VAR:=READ
END;
SETPRINT(NULL,"F"); COMMENT ECHO;
PRINT(VAR,NEWLINE);
SETPRINT(NULL,"C")
END};
PROCEDURE !FIRST;
BEGIN SETFORMAT(13,7); SETPRINT(NULL,"B")
END;
REQUIRE !FIRST INITIALIZATION;
REAL T,U,V,W,X,Y,Z;
INTEGER I,J,K,L,M,N;
STRING S,S1,S2;
The following is a program which uses most of the capabilities of the
above preamble.
BEGIN
REQUIRE "PREAMB.SAI" SOURCE!FILE;
REAL SUM,SUMSQ;
COMMENT SUM AND SUM OF SQUARES OF INPUT DATA;
PROMPTREADCHECKECHO({HOW MANY DATA?"},N,N LEQ 0);
SUM:=SUMSQ:=0.0;
PRINT("DATA IN RANGE 0:100,NEWLINE);
FOR I UPTO N DO
BEGIN
PROMPTREADCHECKECHO({I,":"},{T},T<0 OR T>100);
SUM:=SUM+T;
SUMSQ:=SUMSQ+T*T
END;
PRINT("MEAN=",SUM/N,"DEVIATION=",SQRT(SUMSQ/N-(SUM/N)**2),NEWLINE);
I:=1;
WHILE I NEQ 0 DO
BEGIN
PROMPTREADECHO({"NUMBER TO SQUARE"},{I});
PRINT("SQUARE IS",I*I,NEWLINE)
END
END
with output:
HOW MANY DATA? 2
DATA IN RANGE 0:100
1: 80.00000
2: 90.00000
MEAN= 85.00000 DEVIATION= 5.000000
NUMBER TO SQUARE 16
SQUARE IS 256
NUMBER TO SQUARE 5
SQUARE IS 25
NUMBER TO SQUARE 121
SQUARE IS 14641
NUMBER TO SQUARE 0
SQUARE IS 0
%SAIL Input from Files%.
A SAIL program can take its input from one or more files, as well as from
the terminal. Communication from file to program is via a %channel%, which
you can think of as a pipe through which numbers or other data can flow on
request. There are 16 channels, numbered 0 to 15 . A program, in order
to take input from file MYFILE.DAT , must first connect some channel, C , to
MYFILE.DAT by the command
ASSIGN!CHANNEL(C,"MYFILE.DAT");
where C is a number between 0 and 15 . Now READ(C) is an expression
whose value is a number obtained from channel C , which in turn will get it
from the file MYFILE.DAT.
The following program takes its input from two files, ESTIMT.DAT and
MEASUR.DAT, using channels 1 and 2. It compares numbers in corresponding
positions on the files, for the first three positions, and prints a message
for each position in which the numbers are not equal.
COMMENT FILE[R.RWF]TRY2FL.SAI;
BEGIN
REQUIRE "PREAMB.SAI" SOURCE!FILE;
ASSIGN!CHANNEL(1,"ESTIMT.DAT");
ASSIGN!CHANNEL(2,"MEASUR.DAT");
FOR I UPTO 3 DO
BEGIN
X:=READ(1);
Y:=READ(2);
IF X NEQ Y THEN PRINT("FILES DIFFER IN POSITION",I,NEWLINE)
END
END
Prompting is not needed when reading from files. Because data from a file
ordinarily can not be corrected, programs usually need not provide for
rereading invalid data files. However, checking for invalid data and echoing
input data remain good programming practice. If input data from a file fails
to pass tests for validity, the program may be stopped by the command
USERERR(0,0,"your error message")
which will print your message describing what went wrong, some information
which you will not be able to decipher, and a question mark, before stopping
the program.
%Example%. Program to read two numbers from DIVISN.DAT and print their
quotient:
COMMENT FILE[R.RWF]TRYINF.SAI;
BEGIN
REQUIRE "PREAMB.SAI" SOURCE!FILE;
ASSIGN!CHANNEL(1,"DIVISN.DAT");
X:=READ(1); PRINT("X=",X,NEWLINE);
Y:=READ(1); PRINT("Y=",Y,NEWLINE);
IF Y=0 THEN USERERR(0,0,"ZERO DIVISOR");
PRINT("X/Y=",X/Y)
END
%Rounding and Truncation%.
SAIL uses three functions, FIXR, UUOFIX, and KIFIX, which, when applied to
any real number, give a corresponding integer. The table below shows what
values they give when applied to numbers from -1 to 1 .
-1 -1/2 0 1/2 1
x --!-------!-------!-------!-------!--
-1 0 1
FIXR(x) -------...!------------...!----------...
(x, rounded)
-1 0 1
UUOFIX ...!------------...!------------...!----...
(the "floor" of x)
-1 0 1
KIFIX ------!...-------------------------...!---------
(truncation)
When a real value is assigned to an integer variable, the normal automatic
conversion uses UUOFIX, so
I := X/3 means I := UUOFIX(X/3)
When a real value is used in a place where an integer is required, the same
normally happens:
A[X/3] means A[UUOFIX(X/3)]
X MOD Y means UUOFIX(X) MOD UUOFIX(Y)
X DIV Y means UUOFIX(X) DIV UUOFIX(Y)
%Example%. To test whether X is a perfect square, compute its square root,
round off to the nearest integer, and test for equality with X :
IF X = FIXR(SQRT(X)) THEN PRINT("PERFECT SQUARE")
%Example%: To count how many shelves of length S can be made from a board
of length B , use UUOFIX(B/S) . Don't use B DIV S for this unless you know
that B and S are integers. If B = 7.2 and S = 2.5 ,
UUOFIX(7.2/2.5) = UUOFIX(2.88) = 2 , correct, but
7.2 DIV 2.5 = (UUOFIX(7.2)) DIV (UUOFIX(2.5)) = 7 DIV 2 = 3 , wrong.
Generally, to find the nearest integer (or milestone, or lunar month,
or ...), use FIXR; to find how many complete ones are included, use UUOFIX.
I think KIFIX is useless, except if that the argument is positive, it agrees
with UUOFIX.
The manual does not define I DIV J . It is probably KIFIX(I/J) . To
check this, try it for I = 4, 5, -4, and -5, J = 3 and -3.
%Desk Checking of Programs%.
It is a mistake to expect the computer to find the errors in your
programs. Many errors are found much more easily by checking methods which
depend on understanding what the program is doing, before the computer ever
sees the program.
The first step is to get a grammatically correct program.
(1) Use a light colored pencil or marking pen to circle each comment, from
the word COMMENT through the semicolon that terminates it, checking that
there is no other semicolon in the comment. From here on, ignore the
comments, as they are ignored by the translator.
(2) Similarly circle each complete definition from DEFINE through the
terminating semicolon, checking that the curly brackets {} are correctly
paired, and that any other semicolons are safely inside the curly
brackets.
(3) Find the first END in the program, and draw a line in the left margin
back to the previous BEGIN. Keep doing this, ignoring BEGINs which
have already been used. This matches the BEGINs and ENDs, showing the
scope of iterations and conditional clauses. It also shows how many
times to indent each line.
Example:
FOR --- DO gets indented as FOR --- DO
BEGIN BEGIN
X:=... X:=
IF ... THEN IF ... THEN
BEGIN BEGIN
X:=... X:=...
PRINT... PRINT...
END END
ELSE ELSE
BEGIN BEGIN
Y:=... Y:=...
Z:=... Z:=...
END END;
PRINT... PRINT...
END; etc. END; etc.
(4) Circle the primitive commands, using a different light color. These would
include the assignment and print commands. Also circle declarations.
(5) Now circle the larger commands all of whose component commands are
circled, checking that each has one of the forms
BEGIN D ;D ;...;D ;C ;C ;...;C END
1 2 a 1 2 b
IF ... THEN C
1
IF ... THEN C ELSE C
1 2
FOR ... DO C
1
WHILE ... DO C
1
where C ,C ,..., and D ,D ,... have already been circled. Watch
1 2 1 2
for missing or extra semicolons at this stage, and check when you circle
a block that the BEGIN and END match according to the line in the margin.
Example:
BEGIN
REAL X,U ;
IF --- THEN
WHILE --- DO
BEGIN
X:=Y ;
U := V
END
ELSE
FOR --- DO
FOR --- DO
IF --- THEN
PRINT(---)
ELSE
PRINT(---) ;
P:=Q ;
PRINT(---)
END
(6) Check that all variables used are declared, and that all symbols are
defined which should be.
(7) If a variable is used to hold a value at the end of an iteration which
will be needed when the iteration is started the next time (for example,
the sum of a series), check that the variable is always initialized before
entering the iteration.
%Diagnosing Incorrect Results of Programs%.
(1) If the program has survived desk checking and translation, but gives
unexpected results, observe how far the program gave correct results.
The error will ordinarily lie between that part of the program and the
part that would have printed (or done) what you expected. The earliest
symptom is usually the easiest to diagnose, because the effects of the
first error often complicate the later ones.
(2) If you can't see what went wrong, get a more complete picture of what the
program is doing. At the bottom in each iteration, put
PRINT("identification",variable,count:=count+1)
where "identification" might be "A" , "B" , or "C" , variables is
all the variables of the program, and count is a new variable to keep
track of how many times this part of the program is executed. Plan to
remove these PRINTs when the program runs correctly. An easy way to do
this is to
DEFINE DIAGNOSE(I,V,C) =
{PRINT(I,V,C:=C+1};
until the bugs are out, then to change the second line to
;
(3) To use the results of such diagnostic prints, check whether the variables
satisfy their intended relations. Is there a variable that doesn't change
when it should? Do the variables have the right sign? Does the value
have a decimal point? (An easy mistake is to declare a variable INTEGER
which should be REAL.)
(4) Before accepting a program as correct, make sure that every part gets
executed at least once. Use it on data that cause it to try the ELSE
branch of each conditional command, for instance.
(5) If it is too hard to follow what the program is doing on the assigned
data, change it to work on an analogous but smaller problem. Instead
of computing
1 + 1/2 + 1/3 + ... + 1/10000 ,
compute
1 + 1/2 + 1/3 + ... + 1/N ,
and use
DEFINE N=4;
later, change the 4 to 10000 . Where possible, test the program on
data for which you know or can check the results.
(6) Don't make random changes in your program just to see if something will
happen. Even if it makes your program give correct results on the given
data (it seldom will), it usually leaves the program with bugs. If
necessary, rethink the design of the program and write it out again from
scratch. I once did that for a 4000-line program, and saved myself much
labor by not having to find all the bugs in my junky first draft. In the
process, I was able to simplify the program and make it more efficient.
%Computing with Strings in SAIL%.
A string is a sequence of characters appearing on the keyboard. These
include the visible characters, such as " A ", " 1 ", " + ", and " ( ", and
such invisible characters as the space and return. An expression having a
particular fixed string as its value can be written by enclosing that string
in double quotation marks, as a string constant: "ABC" has the string ABC
as its value and repeating any occurrence of the double quote mark in the
string. "SAY ""AH""" has the string SAY "AH" as its value. If an
expression having a string as its value appears in a PRINT command, the
string is printed. PRINT("P+Q") prints the three characters P+Q .
A string variable may have any string as its value. Such a variable is
declared by writing
STRING I ,I ,...,I
1 2 n
as a declaration that the identifiers I to I are string variables.
1 n
Such string variables can be given values by assignment:
BEGIN prints ABCABC
STRING S1,S2;
S1:="ABC";
S2:=S1;
PRINT(S1,S2)
END
If S is a string expression, we may write an expression for its I-th
through its J-th characters as S[I TO J] . An expression for the string
consisting of J characters beginning with the I-th position in S is
written S[I FOR J] .
%Example%:
STRING S1;
S1 := "ABCDEFGHIJ";
PRINT(S1[2 TO 4], S1[6 FOR 4])
prints the string "BCDFGHI" . Note that the quote marks just written do not
appear in the output; they are part of the name of the string, not part of the
string, and it is the string itself which gets printed. This is unlike the
situation with numbers. The number we call 13 has many names (13.00 ,
26/2 , XIII , etc.) and a computer program can only print these names; the
number itself is an abstraction, and can neither be seen nor be printed.
We may join together the values of two string expressions S1 and S2
by writing S1 & S2 .
%Example%.
STRING ARRAY SA[1:3];
SA[1] := "ABC";
SA[2] := "DE";
SA[3] := SA[1] & SA[2];
PRINT(SA[3])
prints the string "ABCDE" .
The function LOP(SV) has as its value the first character of the string
variable SV (LOP may only be applied to variables), but has the additional
effect of removing the first character of SV . If SV has the value
"123456" , the command
PRINT("$",LOP(SV),LOP(SV),".",LOP(SV),LOP(SV))
prints the string "$12.34" and assigns SV the new value "56" .
The function LENGTH(S) applied to a string gives the length of that
string. The string constant NULL has as its value the null string, the string
of length 0 . The relation EQU(S1,S2) is true if S1 and S2 are exactly
the same string, with the same length and the same characters in corresponding
places. Watch out for the fact that EQU("AB","AB ") and EQU(" AB","AB ")
are both false. Warning: the equal sign, as in IF S1 = "AB" , does not work
for strings. Avoid it!
A piece of program to print the value of S , with asterisks inserted
between characters, but not after the last character:
WHILE LENGTH(S) > 1 DO
PRINT(LOP(S),"*");
PRINT(S)
To put in S2 the reverse of the string initially in S1 :
S2 := NULL;
WHILE NOT EQU(S1,NULL) DO
S1 := LOP(S1) & S2
To read a string value, use either of the expressions READSTRING and
READLINE. READSTRING looks for a string constant (quoted) from the input
keyboard or file, and takes the value of that string constant as its value.
READLINE skips any input line which has already been partially read, and
takes the next complete line, omitting the final return, as its value.
In the program
REAL X; STRING S1,S2;
X1 := READ;
S1 := READSTRING;
S2 := READLINE
with input lines
3.14 "THIS" IS
IT
X will get the value 3.14 , S1 the value "THIS" , S2 the value "IT" ,
and IS will be skipped.
If I is an integer, CVS(I) is the string which would be printed by
PRINT(I) , depending on the use of SETFORMAT . After SETFORMAT(13,7) ,
CVS(1000-1) would be "bbbb999" . The inverse function, CVD(S) , applied
to a (possibly signed) string of digits possibly surrounded by blanks, gives
the corresponding integer value. The function CVF(X) , applied to a real
number X , is the string which would be printed by PRINT(X) . Two similar
functions which give slightly different strings are CVE and CVG. Look up the
function names in the index of the SAIL manual for details.
%Procedures as a Way of Defining Functions in SAIL%.
The LOTS implementation of SAIL includes no built-in function to round
a REAL value to the nearest integer. If we can find a command that computes
the function we want, we can define a new integer function ROUND(X) , for
real arguments X , by the %procedure declaration% (it describes a procedure
for computing the function):
INTEGER PROCEDURE ROUND(REAL X);
BEGIN
INTEGER I;
I := X+0.5;
RETURN(I)
END
A procedure declaration begins with the type of its result, then PROCEDURE,
then the name of the function being defined, then, in parentheses, declarations
for the arguments. There follows a semicolon, and a command for computing the
function. In that command, the command RETURN(Z) will give the value of the
expression Z to the function and terminate the computation of the function.
A similar function, to get FLOOR(X) , the largest integer which does not
exceed X :
INTEGER PROCEDURE FLOOR(REAL X);
BEGIN
INTEGER I;
I:=X;
RETURN(I)
END
%Testing for Equality and Near-Equality%.
Because every step of arithmetic on real numbers potentially introduces a
small error (as much as 0.00000001 times the true result), and because these
errors can accumulate through a long computation, it is dangerous to try to
stop a computation by testing two real numbers for equality. For example, if
we try
X:=0;
WHILE X NEQ 1 DO X := X + 1/3
we will almost certainly have a non-terminating computation. While the actual
computation is done with binary numbers, we can see what would happen on a
three-digit decimal machine, where X would successively become .333 , .666 ,
.999 , 1.32 (or 1.33 ), 1.65 (or 1.66 ), etc., but would never be
exactly 1 . We can handle this by testing whether X differs from its target
value by a small difference:
WHILE ABS(X - TARGET) > SMALL DO ...
where SMALL would be a small number, depending on the expected accuracy of
the computation. We could test whether the ratio of X to its target value is
very close to 1 :
WHILE ABS((X - TARGET)/TARGET) > SMALL DO ...
A related method, when X is converging to a target value, is to keep the
two most recent values of X and test whether they are sufficiently close to
each other.
A related difficulty arises in testing whether a real number is (or is
very close to) exactly an integer. For example, to check if X is a perfect
square, we might want to test if SQRT(X) is an integer. It is tempting to
try:
INTEGER I;
I := SQRT(X); COMMENT INTEGER PART OF ROOT;
IF I**2 = X THEN ...
Several dangers arise. If the true value of X is 25 , computational error
may have made it slightly less, or the inherent limitations of the square root
computation may make the computed square root come out less than 5 . Then I
will get the value 4 , and the test will fail. Worse yet, if the true value
of X is zero, effects of small errors may make it slightly negative, and the
square root can not be calculated. Taking the square root of X + some small
number, say
I := SQRT(X + 1/2);
IF ABS(I**2 - X) < SMALL THEN ...
relieves all these problems. More often, the solution would be to round the
value assigned to I to the nearest integer, rather than the next lower.
%Design of Conditional Commands%.
Let us design a program to print on one page an ornamental letter B ,
as shown in the diagram below.
[FIGURE]
The first part of the diagram shows how the letter should appear; the second
shows the geometrical parameters of the shaded region. The letter is assumed
to be symmetrical about its horizontal center line, and all the lines are
assumed to be one inch wide. We recall that the computer prints characters at
a vertical spacing of one sixth of an inch, and a horizontal spacing of one
tenth of an inch. We shall use asterisks (*) to fill the shaded area of the
letter. The dot at the center of the left edge of the "B" will be used as
the origin of a Cartesian coordinate system.
In outline, a program to print such a letter might be:
FOR L:=1 STEP 1 UNTIL 60: COMMENT PRINT THE L-TH LINE ON THE PAGE;
BEGIN
FOR C:=1 STEP 1 UNTIL 132 DO: COMMENT PRINT THE C-TH CHARACTER ON THE LINE;
1. Choose between printing a blank and an asterisk as the C-th
character of the L-th line of the page;
PRINT(NEWLINE)
END
We are left with the problem of designing a method of deciding whether
the character at a given row and column of the page is inside the shaded region
or not. A first step is to determine the Cartesian coordinates of the point
at which the character will be printed. We simplify the problem slightly by
taking into account the symmetry; we take the absolute value of the vertical
coordinate, since the decision for the point (x,y) is the same as for the
point (x,-y) ; this is why we placed the origin on the letter's horizontal
axis of symmetry. We now express the central iterated command of the program
as
COMMENT 1;
BEGIN
REAL X,Y;
X := (C-40)/10;
Y := ABS(L-30.5)/6;
COMMENT THE ORIGIN LIES BETWEEN THE 30TH AND 31ST LINES, AT THE 40TH
COLUMN, AND C-40 IS THE NUMBER OF COLUMNS RIGHT OF THE ORIGIN WE ARE,
AT 10 COLUMNS PER INCH.;
1.1 Choose between printing a blank and an asterisk at the point (X,Y) on the
page, where Y >= 0.
END
Here, however, we need only consider values of X,Y which fall in the
rectangle shown below:
[FIGURE]
We may observe that this figure consists of straight lines in the region
X <= 5 , and curved lines in the region X > 5 ; thus a natural first step
is to test whether X > 5 or not. We then have
COMMENT 1.1;
IF X > 5 THEN
1.1.1 Choose between printing a blank and an asterisk for (X,Y) known
to be in region B of the diagram below
ELSE
1.1.2 Choose between blank and asterisk for (X,Y) in region A
[FIGURE]
The first test can easily be rewritten, first calculating the distance
from the common center of the circles:
COMMENT 1.1.1;
BEGIN
REAL DISTANCE;
DISTANCE := SQRT((X-5)**2 + (Y-1.75)**2);
IF DISTANCE > 2.25 THEN PRINT("b")
ELSE COMMENT DISTANCE <= 2.25;
IF DISTANCE >= 1.25 THEN PRINT("*")
ELSE COMMENT DISTANCE < 1.25;
PRINT("b")
END
The second test may be further simplified by separating it into two cases,
according as Y >= 3 or Y < 3 :
COMMENT 1.1.2;
IF Y >= 3 THEN
1.1.2.1 Choose between blank and asterisk for a point known to be in
region AA
ELSE
1.1.2.2 Choose for a point known to be in region AB
[FIGURE]
After a final decomposition of the remaining tests, we have the program which
follows:
FOR L:=1 STEP 1 UNTIL 60 DO COMMENT PRINT L-TH LINE;
BEGIN
FOR C:=1 STEP 1 UNTIL 132 DO COMMENT PRINT C-TH CHARACTER;
BEGIN
REAL X,Y COMMENT COORDINATES;
X := (C-40)/10;
Y := ABS((L-30.5)/6);
COMMENT THE ORIGIN LIES BETWEEN THE 30TH AND 31ST LINES, AT THE
40TH COLUMN;
IF X > 5 THEN COMMENT REGION B;
BEGIN
REAL DISTANCE
DISTANCE := SQRT((X-5)**2 + (Y-1.75)**2);
IF DISTANCE > 2.25 THEN PRINT("b")
ELSE COMMENT DISTANCE <= 2.25
IF DISTANCE >= 1.25 THEN PRINT("*")
ELSE COMMENT DISTANCE < 1.25;
PRINT("b")
END
ELSE COMMENT REGION A;
IF Y >= 3 THEN
IF Y > 4 THEN PRINT("b")
ELSE IF X >= -1 THEN PRINT("*")
ELSE PRINT("b")
ELSE IF X < 0 THEN PRINT("b")
ELSE IF X <= 1 THEN PRINT("*")
ELSE IF Y > 0.5 THEN PRINT("b")
ELSE PRINT("*")
END
END
The above example illustrates that a complicated decision can often be
expressed as a series of tests, each of a simple condition. In a command of
the form
IF E THEN C ELSE C
1 2
it is possible to simplify the design of C by using the knowledge that when
1
C is executed, we know that E is true; similarly, in designing C , we
1 2
need treat only the case that E is false. Often, there is a choice of what
condition to test first. The resulting program is simplest if the condition
is so chosen that, as far as possible, no other condition need be tested in
both C and C .
1 2
%Exercise%. Simplify the above program by using the logical connectives in
the conditions. For example, lines 14-18 could be written
IF DISTANCE > 2.25 OR DISTANCE < 1.25 THEN
PRINT("b")
ELSE PRINT("*")
%Exercise%. Print another letter, perhaps F or N or R , in a similar
fashion.
%Exercise%. Print such a letter in italic (slanting) style.
%More Operators and Functions%.
In addition to the familiar arithmetic operators, and functions of
analysis, whose representation in SAIL has already been described, there are
a number of others, less familiar, but of considerable importance in
programming.
(1) E DIV E , E MOD E
1 2 1 2
The value of E DIV E is the integer part of the quotient a /a ,
1 2 1 2
where a and a are integers, discarding any remainder; a typical use is
1 2
to find how many objects of length a can fit in a space a . Thus, if one
2 1
cuts up a plank of length A and width B , into shelves of length C and
width D , the number of shelves which can be made is computed by the
expression (A DIV C)*(B DIV D) . The expression E MOD E designates the
1 2
remainder of the division a /a . For example, the length of the piece of
1 2
plank left over in the process described above, could be computed by the
expression A MOD C .
[FIGURE]
11 DIV 4 = 2 ; 11 MOD 4 = 3
58 DIV 16 = 3; 58 MOD 16 = 10
3 X 2 = 6
In most usage of DIV and MOD, a and a are positive numbers. In this
1 2
case, a div a is the number of times a could be subtracted from a
1 2 2 1
without getting a negative number, and a rem a is the result of these
1 2
subtractions.
The MOD operator is a periodic function of a (at least, as long as a
1 1
is positive); if a is an integer and does not change, and a goes through
2 1
the series of values 0,1,2,3,... , the value of a mod a becomes
1 2
successively 0,1,2,...,a -1,0,l,2,...,a -1,0,1,2,... ; because of this, when
2 2
we want a certain process carried out periodically during an iteration, we
typically use the MOD operator (in the form I MOD P , where I is the
iteration variable and P is the period) as part of the condition which
determines whether the process is carried out. For example, to print a blank
line after every five lines of a table, one might write
FOR I:=1 STEP 1 UNTIL 100 DO
BEGIN
PRINT(I,SQRT(I),NEWLINE);
IF I MOD 5 = 0 THEN
PRINT(NEWLINE)
END
As another example of the use of DIV and MOD, suppose we want to print a
table of roots with A entries, placing B of them on each line, with the
last line perhaps partially full; we might decompose the problem in either of
two ways. In the first, we iterate, A times, the printing of the square
root, afterwards going on to a new line if the number whose root is taken is
a multiple of B , i.e., if I MOD B = 0 , thus:
INTEGER A,B;
A := READ;
B := READ;
FOR I:=1 STEP 1 UNTIL A DO
BEGIN
PRINT(SQRT(I));
IF I MOD B = 0 THEN
PRINT(NEWLINE)
END
In the second decomposition, we iterate first over the lines of printing,
thus:
INTEGER A,B;
A := READ;
B := READ;
FOR I:=1 STEP 1 UNTIL A DIV B DO
Print the I-th full line
Print A MOD B leftovers
The design of this program is simplified by observing:
(1) The number of full lines is F = A DIV B .
(2) The number of items on the first I lines (I <= F) is I*B .
(3) The I-th line (I <= F) thus contains the square roots of the numbers
from (I-1)*B+1 through I*B .
(4) The line of leftovers contains the square roots of the numbers from
(F*B)+1 through A .
The program is then:
INTEGER A,B,F;
A := READ;
B := READ;
F := A DIV B; COMMENT NUMBER OF FULL LINES
FOR I:=1 STEP 1 UNTIL F DO COMMENT I COUNTS LINES;
BEGIN
FOR J := (I-1)*B+1 STEP 1 UNTIL I*B DO
PRINT(SQRT(J));
PRINT(NEWLINE)
END
FOR J := F*B+1 STEP 1 UNTIL A DO
PRINT(SQRT(J))
Observe that in this instance, taking the computation and printing of a
single square root as the iterated command resulted in a simpler program than
using the printing of a line as the iterated unit. Often there are several
ways of looking at the structure of a computational task, and one may be a
simpler description, leading to a simpler program, than another.
(2) ABS(E)
The absolute value, or magnitude, of a . The most important use of this
operator is to measure the difference ABS(A-B) between two numbers A and B.
(3) IF E THEN E ELSE E
1 2 3
This %conditional expression% uses conditions to select between several
alternate expressions, just as the conditional command selects between
alternate commands. The condition E is evaluated. If true, the value a
1 2
of E is the value of the whole expression. If false, a is the value of
2 3
the whole.
%Example%.
FOR I:=1 STEP 1 UNTIL 5 DO
PRINT(I,"IS ", IF I < 0 THEN "NEGATIVE"
ELSE IF I=0 THEN "ZERO"
ELSE IF I > 0 THEN "POSITIVE", NEWLINE)
The example below shows how a command containing a conditional expression
can be looked upon as an abbreviation for a conditional command:
X := (IF A > 5 THEN 2*A IF A > 5 THEN
ELSE IF A < 3 THEN A-2 IF B=C THEN
ELSE 13) X := 2*A+2
+ (IF B=C THEN 2 ELSE 3) ELSE
X := 2*A+3
ELSE
IF A < 3 THEN
IF B=C THEN
X := A-2+2
ELSE
X := A-2+3
ELSE
IF B=C THEN
X := 13+2
ELSE
X := 13+3
The following graphs of expressions show further examples of use of
conditional expressions:
[FIGURE]
IF X >= 0 THEN X IF X >= 0 THEN 1 ELSE -1 IF X >= 0 THEN X ELSE NEG 0
ELSE -X
[FIGURE]
IF X >= 1 THEN 1 IF ABS(X) > 1 THEN 1/X
ELSE IF X <= 0 THEN 0 ELSE X
ELSE X
%Exercise%. The 1972 social security tax on annual income is 5.2% on the
first $7,800.00. If the program variables Y and P contain, respectively,
my previous pay during the current year, and my pay this month, write an
expression for my social security tax this month.
%Solution%. IF Y >= 7800 THEN 0
ELSE IF Y+P >= 7800 THEN 0.052*(7800-Y)
ELSE 0.052*P
The following is not valid for SAIL (FLOOR and ROUND).
(4) FLOOR(E)
The largest integer which does not exceed a ;
a-1 < floor(a) <= a
(5) ROUND(E)
The value of a , rounded to the nearest integer. It has the same sign
as a , and its magnitude is defined by
ABS(ROUND(a)) = floor(a + 1/2)
If one computes a number X which would be an integer except for the effect
of small computational errors, ROUND(X) gives the exact integer value.
[FIGURE]
%Example%.
The British monetary system is undergoing a conversion to a decimal
system,
1 pound = 20 shillings = 240 pence
1 shilling = 12 pence.
Under the new,
1 pound = 100 new pence.
Tables are available to convert from old to new currency. The value of
S shillings plus D pence is
S/20 + d/240 pounds, or
100(s/20 + d/240) = 5(s + D/12) new pence.
This is not always an integer; to round to the nearest integer, one would
write in SAIL:
P := ROUND(5*(S + D/12))
To convert in the other direction, given P new pence, we would first find
the total number of old pence by
T := ROUND(12 * P/5)
This can be broken down into shillings and (old) pence by
S := T DIV 12;
D := T MOD 12
%Example%.
After computing a sales tax exactly (in dollars), one wants to round it
to the nearest hundredth (i.e., cent). If T is the exact figure in dollars,
100*T is the exact figure in cents, ROUND(100*T) is the rounded figure in
cents, and ROUND(100*T)/100 is the rounded figure in dollars.
%Exercise%. One meter is 39.37 inches. One centimeter is 1/100 of a
meter. Write a program to print a conversion table from centimeters to feet
and inches, rounded to the nearest inch. Tabulate from 1 to 100
centimeters. Be careful that the logic of your solution is correct;
30 centimeters, for example, is 11.911 inches, and it is easy to write a
program which mistakenly converts it to 0 feet 12 inches, or even
1 foot 12 inches.
%Exercise%. The number pi , to ten decimal places, is 3.141592654 .
A familiar fractional approximation to pi is 22/7 , or 3.1428 , which is
in error by about 0.0012 . Find a fraction a/b , where b is less than
1000 , which is in error by less than 0.0001 . (There is one such fraction
which differs from pi by only about 0.00003 .)
%Avoiding Redundant Effort in Programming%.
Suppose we have read into an array NAME[1:100] the names of the players
in a tournament, and into SCORE[1:100] their scores. Now we want the program
to print out the name of the player with the highest score (we will assume the
scores are all different, for simplicity). One approach is to try each player
in turn, and check his score against all the scores, printing his name if no
other score is higher. A program to do this might be:
BEGIN
(declarations)
FOR P UPTO 100 DO
COMMENT CHECK IF P IS WINNER;
BEGIN
Q:=1;
WHILE Q LEQ 100 AND SCORE(P) > SCORE(Q) DO
Q := Q+1; COMMENT P BEATS PLAYERS UP TO Q;
IF Q > 100 THEN PRINT(NAME[P])
END
END
This program is correct, but needlessly complex, and can run as much as
five thousand times through the inner iteration (if the scores are in
increasing order). The program does not have the common sense knowledge built
in that we would have; if player P beats everybody on the list before
player Q , then nobody before player Q has any chance, and we should
continue by comparing player Q's score against those of all the following
players on the list. So we need to search the array only once, remembering
only two facts about the part of the array we have already seen: the best
score so far, and who had it.
A program based on this idea is the following:
BEGIN
(declarations, etc.)
BESTPLAYER := NAME[1];
BESTSCORE := SCORE[1];
FOR I:=2 STEP 1 UNTIL 100 DO
IF SCORE[I] > BESTSCORE THEN
BEGIN
BESTSCORE := SCORE[I];
COMMENT BEST OF FIRST I SCORES;
BESTPLAYER := NAME[I]
COMMENT BEST OF FIRST I PLAYERS;
END;
PRINT(BESTPLAYER)
The general idea is to record all the useful information that can be kept from
the part of the computation done so far.
Suppose we want to compute e for a small value of x , using the
formula:
2 3 4 9
e = 1 + x/1 + x /2! + x /3! + x /4! + ... + x /9!
The most obvious method uses an outer iteration to run through the terms which
are being added, and an inner iteration to calculate the factorials. This
involves much wasted effort, because when we have computed 3! , we don't
have to start from scratch to compute 4! ; we only have to multiply 3!
3
by 4 . In fact, once we have x /3! , we only have to multiply by x and
4
divide by 4 to get x /4! . A program based on this follows:
BEGIN
(declarations)
READ(X);
SUM := 1;
TERM := 1;
FOR I UPTO 9 DO
BEGIN
TERM := TERM * X/I; COMMENT X**I/I!;
SUM := SUM + TERM COMMENT SUM OF TERMS UPTO DEGREE I;
END
END
Again, we have arranged to keep all the information we can for later use.
The variable TERM holds enough useful information that we can get the new
summand at the next value of I with just a multiplication and division.
Let's try doing the same thing with a more complicated formula, for
pi/6 :
1 1 1.3 1.3.5
arc sin(1/2) = - + ------- + --------- + ----------- + ...
2 3 5 7
2 .2 .3 2 .2.4 .5 2 .2.4.6 .7
where we have circled the part of each summand that is useful in computing
the next one to the right. To compute this by hand, we might set up this
table:
Q C S
1 1
- 1 -
2 2
1 1 1
---- 3 - + ------
3 2 3
2 .2 2 .2.3
1.3 1 1 1.3
------ 5 - + ------ + --------
5 2 3 5
2 .2.4 2 .2.3 2 .2.4.5
1.3.5 1 1.3.5
-------- 7 - + ... + ----------
7 2 7
2 .2.4.6 2 .2.4.6.7
etc.
In each row after the first, we get the number in column Q from the
one above it by multiplying by C/(4(C+1)) , where C is the number in
column C on the line above. We get the number in column C by adding
2 to the one above. We get the number in column S by adding Q/C (from
the same row) to the number above in column S . The arrows show where the
information comes from that is used to compute each of the numbers. No
number is used again after the number below it is calculated. Because of
this, we can design a computer program to do the same calculations, using
one variable for each column.
BEGIN
(declarations)
Q := 1/2;
C := 1;
S := 1/2;
FOR I UPTO BIGENOUGH DO
BEGIN
Q := Q*C/(4*(C+1));
C := C+2;
S := S + Q/C
END;
PRINT("PI/6",S)
END
A way to do this kind of problem systematically starts by deciding what
we need to compute each time through the iteration. For example, the third
1 1 1.3 1.3.5
time through, we want to end up with - + ------ + -------- + ---------- .
2 3 5 7
2 .2.3 2 .2.4.5 2 .2.4.6.7
In order to get it and to save the useful information needed for the next
stage, we must not only have the sum of the first three terms (left from the
1.3.5
second time through) but also the values -------- (to be saved for use
7
2 .2.4.6
the next time through) and 7 . We want to give these three values to
variables, assuming that the corresponding values were left in those variables
the previous time through the iteration. That is, assume that before the
iteration, we have
1.3 1 1 1.3
Q = ------ C = 5 S = - + ------ + --------
5 2 3 5
2 .2.4 2 .2.3 2 .2.4.5
and we want to make
1.3.5 1 1 1.3 1.3.5
Q = -------- C = 7 S = - + ------ + -------- + ----------
5 2 3 5 7
2 .2.4.6 2 .2.3 2 .2.4.5 2 .2.4.6.7
The two lines above, which describe what each of the variables holds at a
certain moment of the computation, are called %snapshots%. Often, the design
of an iteration is best approached by asking what the typical snapshot should
look like, remembering that each one has to contain enough information to
allow computing the next one. When we have designed the typical one, we work
back to the first one, and the program now is schematically
Assign the variables the values they need for the first snapshot;
FOR I:=2 STEP 1 UNTIL N DO
From the values in snapshot I-1, compute and assign the values
the variables require in snapshot I.
Another snapshot example: look at the series of numbers
0 0 0 1 1 2 3 6 10 18 31 55 ...
where each number after the fourth is the sum of the numbers four places to
its left, two places to its left, and one place to its left; for example,
2+6+10 = 18 . A snapshot that works in computing this series of numbers,
consists of five consecutive numbers, of which four are leftovers from the
previous stage, and the fifth is obtained by adding the first, second, and
fourth: from A = 1 , B = 2 , C = 3 , D = 6 , E = 10 , we want to get
A = 2 , B = 3 , C = 6 , D = 10 , E = 18 , which can be done by
A := B ; B := C ; C := D ; D := E ; E := A+C+D. A complete program is then
BEGIN
(declarations)
PRINT(A:=0,B:=0,C:=0,D:=1,E:=1);
FOR I:=6 STEP 1 UNTIL BIGENOUGH DO
BEGIN
A:=B; B:=C; C:=D; D:=E;
E := A+C+D;
PRINT(E)
END
END